Heap implementation of Priority Queue

maxheap

The root contains the item with the largest search key.

minheap

Place the item with the smallest search key in its root.

semiheap

The item in the root is out of place.

heapDelete

rootItem = items[0]
items[0] = items[size-1]
--size
heapRebuild(items, 0, size)

heapDelete requires 3*⌈log₂(n+1)⌉+1

heapRebuild

heapRebuild(inout items:ArrayType, in root:interger,
in size:interger)
// Conberts a semiheap rooted at index root into a heap.
//Recursively trickle the item at index root down to
//its proper position by swapping it with its larger
//child, it the child is larger than the item.
//If the item is at aleaf, nothing needs to be done.

if (the root is not a leaf)
{    //root must have a left child
child = 2 * root + 1 //left child index

if (the root has a right child)
{    rightChild = child + 1 //right child index
if (itemsprightChild.getKey() > items[child].getKey())
  child = rightChild //larger child index
} //end if

//if the item in the root has a smaller search key
//than the search key of the item in the larger
//child, swap items.
if (items[root].getKey() > items[child].getKey())
{
Swap items[root] and items[child]
//transfoer semiheap rooted at child into a heap
heapRebuild(items, child, size)
}    // end if
}    //end if

//else root is a leaf, so you are done

heapInsert

//insert newItem intto the bottom of the tree
items[size] = newItem

//trickle new item up to appropriate spot in the tree
place = size
parent = (place-1)/2
while ( (parent >= 0) and
(items[place] > items[parent]) )
{
Swap items[place] and items[parent]
place = parent
parent = (place-1)/2
}   //end while

Increment size