D-ary min-heap
D-ary heap is a complete d-ary tree filled in left to right manner, in which holds, that every parent node has a higher (or equal value) than all of its descendands. Heap respecting this ordering is called max-heap, because the node with the maximal value is on the top of the tree. Analogously min-heap is a heap, in which every parent node has a lower (or equal) value than all of its descendands.
Thanks to these properties, d-ary heap behaves as a priority queue. Special case of d-ary heap () is binary heap.
Implementation
D-ary heap is usually implemented using array (let's suppose it is indexed starting at 0). Than for every node of the heap placed at index holds, that its parent is placed at index
and its descendands are placed at indexes
. It is also convenient, if the heap arity is a power of 2, because than we can easily replace multiplications used in the tree traversal by binary shifts.
Code
/** * D-ary heap (min-heap) * @author Pavel Micka */ public class DAryHeap<ENTITY extends Comparable> { private final static int EXPAND_RATIO = 2; //how many times should be the underlying array expanded private final static double COLLAPSE_RATIO = 0.25; //how empty must the heap be, to be the underlying collaped private Object[] array; private int d; //parameter d private int size; //size of the heap private int initialSize; /** * Constructor * @param arraySize initial capacity of the heap */ public DAryHeap(int initialSize, int d) { if (d < 2) { throw new IllegalArgumentException("D must be at least 2."); } this.d = d; this.array = new Object[initialSize]; this.initialSize = initialSize; this.size = 0; } /** * Insert element into the heap * Complexity: O(log(n)) * @param i element to be inserted */ public void insert(ENTITY i) { if (array.length == size) { expand(); } size++; int index = size - 1; int parentIndex = getParentIndex(index); while (index != 0 && i.compareTo(array[parentIndex]) < 0) { //while the element is less then its parent array[index] = array[parentIndex]; //place parent one level down index = parentIndex; //and repeat the procedure on the next level parentIndex = getParentIndex(index); } array[index] = i; //insert the element at the appropriate place } /** * Return the top element and remove it from the heap * Complexity: O(log(n)) * @return top element */ public ENTITY returnTop() { if (size == 0) { throw new IllegalStateException("Heap is empty"); } ENTITY tmp = (ENTITY) array[0]; array[0] = array[size - 1]; size--; if (size < array.length * COLLAPSE_RATIO && array.length / EXPAND_RATIO > initialSize) { collapse(); } repairTop(0); return tmp; } /** * Merge two heaps * Complexity: O(n) * @param heap heap to be merged with this heap */ public void merge(DAryHeap<ENTITY> heap) { Object[] newArray = new Object[array.length + heap.array.length]; System.arraycopy(array, 0, newArray, 0, size); System.arraycopy(heap.array, 0, newArray, size, heap.size); size = size + heap.size; array = newArray; //build heap for (int i = newArray.length / d; i >= 0; i--) { repairTop(i); } } /** * Return index of the parent element * @param index index of element, for which we want to return index of its parent * @return index of the parent element */ private int getParentIndex(int index) { return (index - 1) / d; } /** * Place the top of the heap at a correct place withing the heap (repair the heap) * @param bottom last index of the array, which can be touched (is in the heap) * @param topIndex index of the top of the heap */ private void repairTop(int topIndex) { Comparable tmp = (Comparable) array[topIndex]; int succ = findSuccessor(topIndex * d + 1, topIndex * d + d); while (succ < size && tmp.compareTo(array[succ]) > 0) { array[topIndex] = array[succ]; topIndex = succ; succ = findSuccessor(succ * d + 1, succ * d + d); } array[topIndex] = tmp; } /** * Return descendant with the least value * @param from index of the first descendant * @param to index of the last descendant * @return index of the descendant with least value */ private int findSuccessor(int from, int to) { int succ = from; for (int i = from + 1; i <= to && i < size; i++) { if (((Comparable) array[succ]).compareTo((Comparable) array[i]) > 0) { succ = i; } } return succ; } /** * Expand the underlying array */ private void expand() { array = Arrays.copyOf(array, array.length * EXPAND_RATIO); } /** * Collapse the underlying array */ private void collapse() { array = Arrays.copyOf(array, array.length / EXPAND_RATIO); } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (int i = 0; i < size; i++) { builder.append(array[i]).append(" "); } return builder.toString(); } }