## Saturday, January 2, 2016

### 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.}