You won't implement the heap IN binary tree, because the heap is A binary tree. The heap maintains the following order property - given a node V, its parent is greater or equal to V. Also the heap is complete binary tree. I had ADS course at uni so I will give you my implementation of the heap in Java later in the answer. Just to list the main methods complexities that you obtain:
- size() O(1)
- isEmpty() O(1)
- insert() O(logn)
- removeMin() O(logn)
- min() O(1)
Here is my Heap.java file:
public class Heap<E extends Comparable<E>> {
private Object S[];
private int last;
private int capacity;
public Heap() {
S = new Object[11];
last = 0;
capacity = 7;
}
public Heap(int cap) {
S = new Object[cap + 1];
last = 0;
capacity = cap;
}
public int size() {
return last;
}
//
// returns the number of elements in the heap
//
public boolean isEmpty() {
return size() == 0;
}
//
// is the heap empty?
//
public E min() throws HeapException {
if (isEmpty())
throw new HeapException("The heap is empty.");
else
return (E) S[1];
}
//
// returns element with smallest key, without removal
//
private int compare(Object x, Object y) {
return ((E) x).compareTo((E) y);
}
public void insert(E e) throws HeapException {
if (size() == capacity)
throw new HeapException("Heap overflow.");
else{
last++;
S[last] = e;
upHeapBubble();
}
}
// inserts e into the heap
// throws exception if heap overflow
//
public E removeMin() throws HeapException {
if (isEmpty())
throw new HeapException("Heap is empty.");
else {
E min = min();
S[1] = S[last];
last--;
downHeapBubble();
return min;
}
}
//
// removes and returns smallest element of the heap
// throws exception is heap is empty
//
/**
* downHeapBubble() method is used after the removeMin() method to reorder the elements
* in order to preserve the Heap properties
*/
private void downHeapBubble(){
int index = 1;
while (true){
int child = index*2;
if (child > size())
break;
if (child + 1 <= size()){
//if there are two children -> take the smalles or
//if they are equal take the left one
child = findMin(child, child + 1);
}
if (compare(S[index],S[child]) <= 0 )
break;
swap(index,child);
index = child;
}
}
/**
* upHeapBubble() method is used after the insert(E e) method to reorder the elements
* in order to preserve the Heap properties
*/
private void upHeapBubble(){
int index = size();
while (index > 1){
int parent = index / 2;
if (compare(S[index], S[parent]) >= 0)
//break if the parent is greater or equal to the current element
break;
swap(index,parent);
index = parent;
}
}
/**
* Swaps two integers i and j
* @param i
* @param j
*/
private void swap(int i, int j) {
Object temp = S[i];
S[i] = S[j];
S[j] = temp;
}
/**
* the method is used in the downHeapBubble() method
* @param leftChild
* @param rightChild
* @return min of left and right child, if they are equal return the left
*/
private int findMin(int leftChild, int rightChild) {
if (compare(S[leftChild], S[rightChild]) <= 0)
return leftChild;
else
return rightChild;
}
public String toString() {
String s = "[";
for (int i = 1; i <= size(); i++) {
s += S[i];
if (i != last)
s += ",";
}
return s + "]";
}
//
// outputs the entries in S in the order S[1] to S[last]
// in same style as used in ArrayQueue
//
}
HeapException.java:
public class HeapException extends RuntimeException {
public HeapException(){};
public HeapException(String msg){super(msg);}
}
The interesting part that gives you O(logn) performance is the downHeapBubble() and upHeapBubble() methods. I will add good explanation about them shortly.
upHeapBubble() is used when inserting new node to the heap. So when you insert you insert in the last position and then you need to call the upHeapBubble() like that:
last++;
S[last] = e;
upHeapBubble();
Then the last element is compared against it's parent and if the parent is greater - swap: this is done max logn times where n is the number of nodes. So here comes the logn performance.
For the deletion part - you can remove only min - the highest node. So when you remove it - you have to swap it with the last node - but then you have to maintain the heap property and you have to do a downHeapBubble(). If the node is greater than it's child swap with the smallest one and so on until you don't have any children left or you don't have smaller children. This can be done max logn times and so here comes the logn performance. You can explain yourself why this operation can be done max logn times by looking in the binary tree pictures here
