Skip to content

Instantly share code, notes, and snippets.

@arrayed
Created December 30, 2016 18:48
Show Gist options
  • Save arrayed/70d915bc3150c9d7aa538364c1a17056 to your computer and use it in GitHub Desktop.
Save arrayed/70d915bc3150c9d7aa538364c1a17056 to your computer and use it in GitHub Desktop.
Implement D-ary Heap 4-way
/* 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