﻿ ﻿ D-ary 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))
*/
public ENTITY returnTop() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
ENTITY tmp = (ENTITY) array;
array = 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();
}
}


www.EuAutodily.cz SEO od společnosti Digital Pylon

Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online Casino