Created
December 30, 2016 18:48
-
-
Save arrayed/70d915bc3150c9d7aa538364c1a17056 to your computer and use it in GitHub Desktop.
Implement D-ary Heap 4-way
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* heap.java | |
* Class - heap | |
* Authors - Amritpal Singh | |
* Website - arrayed.net | |
* Description - Implement D-ary Heap (4-way in this case each node has 4 children) max heap, each node has priority level and string value associated. | |
*/ | |
public class heap { | |
private heapNode[] heapArray; // heap array of nodes | |
private int maxCapacity; // max capacity of heap set in constructor | |
private int numElements; // keeps a count of number of elements in the heap | |
private int numWays = 4; // 4-way heap, number of children a each node has | |
// heap constructor | |
public heap(int maxSize) { | |
numElements = 0; | |
maxCapacity = maxSize; | |
heapArray = new heapNode[maxCapacity]; | |
} | |
// returns true if heap is empty, otherwise false | |
public boolean isEmpty() { | |
return numElements == 0; | |
} | |
// returns true if heap is empty, otherwise false | |
public boolean isFull() { | |
return numElements == maxCapacity; | |
} | |
// insert() method, insert element in the heap with a priority level and string value | |
public void insert(int priority_level, String string_value) { | |
if (isFull()) | |
System.out.println("Error: heap is full!"); | |
else { | |
heapNode newNode = new heapNode(priority_level,string_value); | |
heapArray[numElements] = newNode; | |
heapUp(numElements); | |
numElements++; | |
} | |
} | |
// heapUp() method, this method compares the inserted element with its parent, | |
// if inserted element is larger we move the parent down, we continue doing this until heap order is correct and insert element in ix. | |
public void heapUp(int ix) { | |
heapNode lastElement = heapArray[ix]; | |
int parentIndex = (ix-1)/numWays; | |
while ((ix > 0) && (lastElement.getPriority() > heapArray[parentIndex].getPriority())) { | |
heapArray[ix] = heapArray[parentIndex]; | |
ix = parentIndex; | |
parentIndex = (parentIndex-1)/numWays; | |
} | |
heapArray[ix] = lastElement; | |
} | |
// delete max element from the heapArray | |
public String delete_max() { | |
heapNode max = heapArray[0]; | |
numElements--; | |
// set the last element as root | |
heapArray[0] = heapArray[numElements]; | |
heapDown(0); | |
return max.priority + " \t\t " + max.getStringValue(); | |
} | |
// heapDown() method, this method compares the replacement element with the max of children, | |
// if the largest child is larger than this replacement element, we move the child up, we continue doing this until heap order is correct and put the replacement element in correct index. | |
public void heapDown(int ix) { | |
int maxChild = findMax(ix*numWays+1,ix*numWays+numWays); | |
heapNode tempRoot = heapArray[ix]; // save root in temp variable | |
while ((maxChild < numElements) && (heapArray[maxChild].getPriority() > tempRoot.getPriority())){ | |
heapArray[ix] = heapArray[maxChild]; | |
ix = maxChild; | |
maxChild = findMax(maxChild*numWays+1, maxChild*numWays+numWays); | |
} | |
heapArray[ix] = tempRoot; | |
} | |
// find maximum of the children | |
public int findMax(int from, int to) { | |
int maxChild = from; | |
for (int i=from+1; (i<=to && i<numElements); i++){ | |
if ((heapArray[maxChild].getPriority()) < (heapArray[i].getPriority())) | |
maxChild = i; | |
} | |
return maxChild; | |
} | |
// heap node class | |
private class heapNode { | |
private int priority; | |
private String string_value; | |
// constructor | |
public heapNode (int priority, String string_value) { | |
this.priority = priority; | |
this.string_value = string_value; | |
} | |
// set priority | |
public void setPriority(int priority) { | |
this.priority = priority; | |
} | |
// get priority | |
public int getPriority() { | |
return priority; | |
} | |
// set string | |
public void setStringValue(String string_value) { | |
this.string_value = string_value; | |
} | |
// get string | |
public String getStringValue() { | |
return string_value; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment