Binary heap

PAL Definice Binární halda

(Minimal) Binary Heap is a tree data structure with following properties

• Every level is full except possibly the last, which is filled from left to right
• if $x$ is a node and $ch$ a child of $x$, then $k(x)\ge k(ch)$

Operations

Insert

Insert (x) {
	Add a node x at the end of the heap; 
	while ( key(parent(x)) > key(x) ) { 
		Swap node x with parent(x); 
	}
}

The while loop is sometimes called bubble up. Depth of heap is $\log (n)$, worst case is bubbling to the root.

Accessing minimum

Constant, just return root of heap.

Removing minimum

Swap root with last element and bubble down.

ExtractMin(){
	Swap first and last node;
	Remove last node;
	x = root;
	while( k(x)>k(l(x)) or k(x)>k(r(x)) ){
		y = least of l(x) or r(x);
		Swap x an y;
		x = y;
	}
}

Delete any node

You get a pointer to a node. So you swap it with the end. Now it violates both sides

Delete(&x){
	Swap contains of x and last node;
	Remove last node;
	
	if(k(x) < k(p(x))){
		bubbleUp(x)
	}
	else{
		bubbleDown(x)
	}
}

DecreaseKey

Just bubble up

DecreaseKey(x, newKey):
    key(x) = newKey
    bubbleUp(x)

Representation

It can be represented in a simple array, which makes it fast (cache is fast).

Indexing can be done as follows, assuming the first index is 1:

• left child - $2k+1$
• right child - $2k$
• parent - $k/2$ or $k>>1$