Priority Queue and Binary Heap

Priority Queue

Data structure with nodes and keys and data  are associated with each node. Total order is defined for the keys.

Its is simple to identify or remove smallest key. But no other key can be identified or removes as easily.

Insertion is possible at any time.

Priority Queue can be represented using Binary Heap.

Binary Heap

A complete binary tree- A tree in which every level is filled except bottom level which is filled in the left to right order.

No child of any node may have key less than its parents key.

Level order traversal gives a sorted list of keys.

Binary heap using Array

A binary heap can be maintained using an array. For any node X with an index i its children are at i*2 and i*2+1. Like for a node with index 3, its children nodes are at 6 nad 7.

Binary heap time complexity

	Average case	Worst case
Search	O(n)	O(n)
Insert	O(lg n)	O(lg n)
Delete	O(lg n)	O(lg n)

Operations

Get min

Just return the node's key at root.

Insert

Place the new key at the boottom of the tree- ie the after the last entry- set this as current node.
Now the entry needs to bubble up untill the heaporder property is satisfied-
    Repeat untill no swap possible
        If current node's key is less than its parents' key swap current node with parent.

Remove min

Remove the root entry and replace root with last item in the tree (array). Then while possible bubble down the entry by comparing and swaping with child that has smaller key than current nodes key untill no swap is possible.

Bottom up heap construction

Insert all the items in the tree any order. That is we can keep the array of numbers as it is.
Take the last internal node and bubble down to tree like removeMin() operation in the heap.