What is a heap?
A (maximum) heap is a complete binary tree having a key associated with each node, the key of each parent node being greater than or equal to the keys of its child nodes
What two operations does the heap ADT support?
insert new element and delete/retrieve maximum element
These both can be performed in O(log n) time.
What is the most common way to represent a heap?
In an array
Inserting a node into heap example
Deleting maximum node in a heap example
What is a priority queue?
A priority queue is a container for a totally-ordered set of elements (ADT)
What operations does a priority queue support?
insert, peek front, delete front, decrease key (i.e. priority of an element)
How is priority queue often implemented
Often is implemented using a binary heap data structure
What can priority queues be used to represent?
Particular kinds of stacks and queues.
The Selection Problem
- We want to find the k-th smallest item (rank k) of an unsorted collection of n elements.
- Can solve by sorting the list then pick the k-th element.
(not very efficient O(n lg n) )
- Using a binary heap we have a Θ(n + k lg n) algorithm.
- There is a Θ(n) algorithm for all input (worst case).
- There is a (simple and practical) known average-case Θ(n) algorithm, derived from quicksort, called quickselect.
- The idea is to do quicksort but only recurse into one of the two partitions that contains the k-th smallest element.
How do you create a selection algorithm that runs in Θ(n) for all input?
ensure that “good” pivots are found
median-of-medians linear-time algorithm
• The divide-and-conquer recursive M.-M. algorithm:
- 1 Partition input of n items into groups of five items.
- Find exact median of each of the 5-element groups.
- Find the median of these dn/5e medians (by recursion) as selected pivot.
