event queues, with event time as key.
Identify or remove entry who's key is lowest.
4: first -> Insert -> 4: first -> removeMin() -> 4: 5: second 5: second
min() - returns 5
Complete Binary Tree. Every level of tree is full. except possibility of bottom row.
Binary Heap can be
Min Heap or
Every Subtree of a Binary heap is a Binary Heap.
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
0 1 2 3 4 5 6 7 8 9 10
|X|2 | 5 | 3 | 9 | 6 | 11 | 4 | 17 | 10 | 8
| v Intentionally left empty.
Mapping of nodes to Indices :
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.
Binary Tree is used when we remove and insert, tree stays compact.
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:2
2 5 3 9 6 11 4 17 10 8