Implement Heap

http://www.programming-algorithms.net/article/41909/D-ary-heap
d-ary heap behaves as a priority queue. Special case of d-ary heap () is binary heap.

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.

005.public class DAryHeap<ENTITY extends Comparable> {

006. 

007.private final static int EXPAND_RATIO = 2; //how many times should be the underlying array expanded

008.private final static double COLLAPSE_RATIO = 0.25;//how empty must the heap be, to be the underlying collapsed

009.private Object[] array;

010.private int d; //parameter d

011.private int size; //size of the heap

012.private int initialSize;

013. 

014./**

015.* Constructor

016.* @param arraySize initial capacity of the heap

017.*/

018.public DAryHeap(int initialSize, int d) {

019.if (d < 2) {

020.throw new IllegalArgumentException("D must be at least 2.");

021.}

022.this.d = d;

023.this.array = new Object[initialSize];

024.this.initialSize = initialSize;

025.this.size = 0;

026.}

027. 

028./**

029.* Insert element into the heap

030.* Complexity: O(log(n))

031.* @param i element to be inserted

032.*/

033.public void insert(ENTITY i) {

034.if (array.length == size) {

035.expand();

036.}

037.size++;

038.int index = size - 1;

039.int parentIndex = getParentIndex(index);

040.while (index != 0 && i.compareTo(array[parentIndex]) < 0) {//while the element is less then its parent

041.array[index] = array[parentIndex]; //place parent one level down

042.index = parentIndex; //and repeat the procedure on the next level

043.parentIndex = getParentIndex(index);

044.}

045.array[index] = i; //insert the element at the appropriate place

046.}

047. 

048./**

049.* Return the top element and remove it from the heap

050.* Complexity: O(log(n))

051.* @return top element

052.*/

053.public ENTITY returnTop() {

054.if (size == 0) {

055.throw new IllegalStateException("Heap is empty");

056.}

057.ENTITY tmp = (ENTITY) array[0];

058.array[0] = array[size - 1];

059.size--;

060.if (size < array.length * COLLAPSE_RATIO && array.length / EXPAND_RATIO > initialSize) {

061.collapse();

062.}

063.repairTop(0);

064.return tmp;

065.}

066. 

067./**

068.* Merge two heaps

069.* Complexity: O(n)

070.* @param heap heap to be merged with this heap

071.*/

072.public void merge(DAryHeap<ENTITY> heap) {

073.Object[] newArray = new Object[array.length + heap.array.length];

074.System.arraycopy(array, 0, newArray, 0, size);

075.System.arraycopy(heap.array, 0, newArray, size, heap.size);

076.size = size + heap.size;

077.array = newArray;

078.//build heap

079.for (int i = newArray.length / d; i >= 0; i--) {

080.repairTop(i);

081.}

082.}

083. 

084./**

085.* Return index of the parent element

086.* @param index index of element, for which we want to return index of its parent

087.* @return index of the parent element

088.*/

089.private int getParentIndex(int index) {

090.return (index - 1) / d;

091.}

092. 

093./**

094.* Place the top of the heap at a correct place withing the heap (repair the heap)

095.* @param bottom last index of the array, which can be touched (is in the heap)

096.* @param topIndex index of the top of the heap

097.*/

098.private void repairTop(int topIndex) {

099.Comparable tmp = (Comparable) array[topIndex];

100.int succ = findSuccessor(topIndex * d + 1, topIndex * d + d);

101.while (succ < size && tmp.compareTo(array[succ]) > 0) {

102.array[topIndex] = array[succ];

103.topIndex = succ;

104.succ = findSuccessor(succ * d + 1, succ * d + d);

105.}

106.array[topIndex] = tmp;

107.}

108. 

109./**

110.* Return descendant with the least value

111.* @param from index of the first descendant

112.* @param to index of the last descendant

113.* @return index of the descendant with least value

114.*/

115.private int findSuccessor(int from, int to) {

116.int succ = from;

117.for (int i = from + 1; i <= to && i < size; i++) {

118.if (((Comparable) array[succ]).compareTo((Comparable) array[i]) > 0) {

119.succ = i;

120.}

121.}

122.return succ;

123.}

124. 

125./**

126.* Expand the underlying array

127.*/

128.private void expand() {

129.array = Arrays.copyOf(array, array.length * EXPAND_RATIO);

130.}

131. 

132./**

133.* Collapse the underlying array

134.*/

135.private void collapse() {

136.array = Arrays.copyOf(array, array.length / EXPAND_RATIO);

137.}

138. 

139.@Override

140.public String toString() {

141.StringBuilder builder = new StringBuilder();

142.for (int i = 0; i < size; i++) {

143.builder.append(array[i]).append(" ");

144.}

145.return builder.toString();

146.}

147.}