2.2. Binary Heap
Operations: swim and sink.
A binary heap is a PQ that takesfor both add()
and remove()
, where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).
When should we use a binary heap over a lazy PQ or an eager PQ?
Balanced Binary Tree
A balanced binary tree can be implemented by a list such that given the 'th key in the list:
The index of its parent:
The index of its left child: .
The index of its right child: .
e.g., given the list
[1, 2, 3, 4, 5]
,1
is the root,2
and3
are the left and right children of1
, and4
and5
are the left and right children of2
, respectively.
Is the tree represented by the list
[1, 2, 3, 4, 5]
balanced?
Implementation
Let us create the BinaryHeap
class inheriting AbstractPriorityQueue
:
L11
: addingnull
as the first item makes it easier to calculate the indices of parents and children.L16
:keys
has the extra item ofnull
fromL11
that is not an input key.
How does adding
null
make the calculation of the indices easier?
Additionally, let us define the helper method compare()
that compares two keys in the list:
L8
: calls thecompare()
method in the member fieldpriority
declared in the super class.
Add()
with Swim
Add()
with SwimThe add()
method in a heap uses the operation called swim as follows:
L3
: appends the new key to the list.L7-10
: keeps swimming until the list becomes a heap:L8
: compares the new key to its parent if exists.L9
: if the new key has a higher priority than its parent,Collections.swap()
them.
How many keys are compared at most for the `add operation?
Remove()
with Sink
Remove()
with SinkThe remove()
method in a heap uses the operation called sink as follows:
L3
: checks if the heap is empty.L4
: swaps the root and the last key in the list.L3
: removes the (swapped) last key with the highest priority in this heap.L10-16
: keeps sinking until the list becomes a heap:L12
: finds the child with a higher priority.L13
: breaks if the parent has a higher priority than the child.L14
: swaps if the child has a higher priority than the parent.
How many keys are compared at most for the
remove
operation?
Last updated
Was this helpful?