Implement D-ary Heap 4-way

heap.java

/* 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;
		}
	}
}