 Bit like dictionary.
 Entries with key and value.
 Total order is defined on the keys
 Any key can be inserted at any time.
 Commonly used as
event queues
, with event time as key.  We can implement using BinaryHeap , Sorted List, Unsorted List
 Uses Data structure  Binary Heap
 Binary heap is an implementation of Priority Queue.
 Stored as arrays of entries by levelorder traversal.
 Storing as Array is faster.
Operations

Identify or remove entry who's key is lowest.
 Limitation : remove other entries are slow. This makes priority queue fast.

Insert:

4: first > Insert > 4: first > removeMin() > 4: 5: second 5: second
7: third

min()  returns 5

Binary Heap

Complete Binary Tree. Every level of tree is full. except possibility of bottom row.

Binary Heap can be
Min Heap
orMax Heap

Every Subtree of a Binary heap is a Binary Heap.
 Bottom row = filled from left to right.
2
5 3
9 6 11 4
17 10 8

Entries will satisfy
heap order
property No child has a key less than parent's key other way to say, Child Key is greater than Parent's key
 Stored in array using levelorder traversal.
0 1 2 3 4 5 6 7 8 9 10 X2  5  3  9  6  11  4  17  10  8
 v Intentionally left empty. 
Mapping of nodes to Indices :
Level Numbering
. 
How to get to Node i Node i's children are 2i & 2i+1 Node i's parent is i/2
so from above example,
To find info about 9 , whose index is 4.
 as per formulae, children are at 2i & 2i +1 = at index 8 & 9 which amounts to values 17 & 10. and parent is i/2 = 4/2 = 2 Value at index 2 is 5 . parent is 5

Binary Tree is used when we remove and insert, tree stays compact.
Operations

min() = return the root. Binary Heap , min value is at the root.

Insert(Object K,Object v) > key has to be comparable.

we bubble up after insert.

X is the new entry

Place X in bottom level at first available slot. If bottom level is full, start new level and fill it from left.

New Key might violate the
heap order
property. So let's insert key:22 5 3 9 6 11 4 17 10 8 [2]
 we need to rebalance.
 Entry will now bubbles up the tree until the heap order property is satisfied.
 Repeat:
 Compare X with its parent key
 If X is less than parent, swap/exchange.


Entry RemoveMin()
 Remove the entry at the root. Root is always minimum.
 Before we return , fix the root, as we rootless.
 Fill the hole with last entry in the tree. (obviously last entry is not minimum value)
 We will bubble it down the heap.
 Repeat:
 If X > one or both of is children. Swap X with
minimum child
 If X > one or both of is children. Swap X with
Comparing for Running Times
Binary Heap
 min () = O(1)
 insert() = Bubbles up
 Worst case = O(log n) , takes O(1) for comparing. has 1+log2n , where n is no.of entries. so it takes O(log n)
 Best Case = O(1) , if you get lucky.
 removeMin()
 Worst case = O(log n)
 Best case = O(1) , if all the items have exactly same key.
Sorted List
 min() = O(1)
 insert()
 W.C = O(n)  we can search using binary search in log n but to insert we have to push other items and that is O(n)
 B.C = O(1)
 removeMin()
 W.C = O(1)
 B.C = O(1)
UnSorted List
 min() = O(n)  Linear Time
 insert()
 W.C = O(1)
 B.C = O(1)
 removeMin()
 W.C & B.C = O(n)  Linear Time
Bottom Up Heap Construction.
 Given set of entries, make a heap out of it.
 Insert one by one : O(log n) time.
 How to do in O(n)  Linear Time.
 Make a complete tree using entries in any order.
 Now Fix the broken Tree.
 Walk Backward from Last internal Node. (node which is not a leaf) i.e : Loop backward in array
 When we visit a node, bubble it down as removeMin()