A container for objects that have keys. 2 operations - Insert and Extract-min or max; both takes place in log(n) time. n being the no. of keys.
Conceptually - think of a heap as a tree - rooted, binary.
Heap Property - at every node x, key[x] <= all keys of x's children
Consequence - object at root must have minimum key value
Array Implementation
parent[i] = i/2 if i is even or floor(i/2) if i is odd.
and children of i = 2i, 2i+1
Use of array is good in terms of storage - no space wasted on pointers. Traversing should be easier.
Insert and Bubble-Up (given key k) Runtime = O(logn)
Applications
Conceptually - think of a heap as a tree - rooted, binary.
Heap Property - at every node x, key[x] <= all keys of x's children
Consequence - object at root must have minimum key value
Array Implementation
parent[i] = i/2 if i is even or floor(i/2) if i is odd.
and children of i = 2i, 2i+1
Use of array is good in terms of storage - no space wasted on pointers. Traversing should be easier.
Insert and Bubble-Up (given key k) Runtime = O(logn)
- Stick k at end of last level
- Bubble-up k until heap property is restored (i.e. key of k's parent is <= k)
No. of levels in heap tree == log(n) [base 2] -> n is no. of items in heap
Extract-Min and Bubble-Down Runtime = O(logn)
- Delete root
- Move last leaf to be new root
- Iteratively bubble-down until heap property has been restored [always swap with smaller child]
Applications
- Sorting: Canonical use of heap - fast way to do repeated minimum computations.
Runtime = O(nlogn) time (Each heap operation has a logarithmic runtime; do it n times!)
- Insert all n array elements into a heap.
- Extract-min to pluck out elements in sorted order
2. Event Manager: Synonym for a heap: Priority Queue.
Example use: Game simulation
Example use: Game simulation
- objects = event records [action/update to occur at given time in the future]
- key = time event scheduled to occur
- Extract-min = yields the next scheduled event
3. Median maintenance
At each time step i, calculate the median of i numbers in O(logi) time.
At each time step i, calculate the median of i numbers in O(logi) time.
- maintain heaps Hlow: supports EXTRACT_MAX; Hhigh: supports EXTRACT_MIN
4. Speeding up Dijikstra from O(nm) to O(mlogn)
No comments:
Post a Comment