Binary Heaps
What
is a Binary Heap?
· A
binary heap is a binary tree, where the value in every node is either less than
the value of its children (minimum heap) or more than the value of its children
(maximum heap). For this unit, we will focus on minimum heap (or, min-heap).
· As
per the above definition, we can conclude that the value of the root in a
min-heap is the least value in the min-heap. Hence, we can access the minimum
in constant time, O (1) by simply returning the value at root.
· Binary
heaps are used to store the priorities of various processes in queuing systems.
This allows for the quick retrieval of the highest priority (typically the
least value).
Implementation
Details:
We will use an integer array to represent our min-heap. Start by
declaring an array of size (=10). Fill it up with six values and define a size
variable, size (of type integer). At the start of our program, size = 6. As we
insert additional values, we will increase the size by 1 each time. As we
delete values from a min-heap, we will decrease of size by 1 each time.
Obviously, we cannot exceed the capacity of 10 in our array. Using an array
significantly simplifies the implementation of a min-heap (and accompanying
methods). Also, using an array to implement the methods for a min-heap does
not result in any reduction in running time (as we will see below).
Let’s say our min-heap looks as below:
2
4 11
15 16 18
We will represent the above min-heap in our array as below:
2 4 11 15 16 18 0 0 0
0
The root is always at Cell#0 (= 2).
The left child of the root is at, 2 * 0 + 1 = 1(Cell#1 = 4).
The right child of the root is at, 2 * 0 + 2 = 2(Cell#2 = 11).
Similarly for 4 (Cell #1), the left child is at, 2*1 + 1 = 3 (Cell#3 =
15) and the right child is at 2*1 + 2 = 4 (Cell#4 = 16)
Finally, for 11 (Cell #2), the left child is at, 2 * 2 + 1 = 5 (Cell
#5 = 18). Since the right child for 11 is at 2*2 + 2 = 6 and it exceeds the
current size of the heap= 6 (Cell#6 = 0, denoting that it’s empty), we can stop
here.
If we wish to find the parent of any value in the min-heap, we simply
divide its cell# by 2 (integer division). Hence, the parent of 15 (Cell#3), is
at Cell# (3/2) = Cell#1 = 4.
To
generalize:
For a cell, i in the min-heap:
· The
left child is found in the cell, 2*i + 1
· The
right child is found in the cell, 2*i + 2
· The
parent is found at cell, i/2
NOTE: If
you don’t like the fixed capacity, you are welcome to use an Array List. On the
other hand, if you wish to use a binary tree to implement a min-heap, you will
navigate the min-heap recursively to implement the above methods (like how we
navigated the binary search trees ).
Methods
for a Min-Heap:
We will start our initial array with stored values that already
satisfy the min-heap property (parent value less than its children values) and
describe the following operations on it:
· Insertion:
adding a new value to the min-heap and maintain the min-heap property.
· Deletion: returning and removing the root value from
the min-heap and maintaining the min-heap property.
Insertion
– O (log n):
· Inserting
a value into a min-heap involves adding the value at the next empty spot in the
last level of the min-heap. Hence, a new value is always inserted initially
as a leaf. After the initial insertion, the value is then “percolated up”
to its proper spot (to ensure the min-heap property) by following the steps
below:
o
Step
#1: Increase the size of the array by 1. Hence size = 5 + 1 = 6. Recall
again that the capacity of our array is fixed (=10). We are only increasing the
values in the array from 5 to 6 by adding an additional value.
o
Step
#2: Insert the new value (say, 1) at array [size]. Hence, in our above
example, a[6] = 1 and the updated array will look as below:
2 4 11 15 16 18 1 0 0
0
o
Step
#3: Starting at Cell# size (=6), successively compare the value at array
[size] and its parent at array [size/2]. If array [size] < array [size/2],
swap the values of the child with its parent. You will do this until you find a
parent value that is less than its child or you have reached the start of the
array (Cell#0). At Cell#0, comparing the values of array [size] and array
[size/2] would be comparing the same value and your loop should terminate. You
have to include Cell#0 in your loop as Cell#0 is the parent of Cell #1. This
step is also called “Percolate Up”.
For our example, Step#3 would be as below:
2 4 11 1 16 18
15 0 0 0
2 1 11 4 16 18
15 0 0 0
1 2 11 4 16 18
15 0 0 0
Returning
O(1) and Deleting the Root Value O(log n) - :
· Since
the minimum is at the root in a min-heap, it makes it very easy to find the
minimum value in a min-heap. We simply return the value at the root (Cell#0) in
O (1). Hence, this method does not take any input values. Typically, we also
want to remove the root value and replace it with the next least value in the
min-heap. We will follow the steps below to find and replace the deleted root
value with the next least value in the min-heap:
o
Step
#1: Store the existing root value in a local variable, temp. We will
return temp after we have replaced its value with the next least value.
Our
array (continuing after insertion) would be as below:
1 2 11 4 16 18
15 0 0 0
The
variable, temp = 1
o
Step
#2: Replace the first value in the min-heap (Cell #0) with its last value
(at Cell#, size-1)
15 2 11 4 16 18
0 0 0 0
o
Step
#3: Decrease the size of the array by 1. Again, the capacity of the array
remains fixed at 10, but the number of values in the min-heap decrease by
1(therefore, size = 6).
o
Step
#4:
This
step is about replacing the current root value with the next least value in the
min-heap to ensure that the min-heap property is maintained. This step is also
called “Percolate down”. We will declare an integer variable, minCell (=0), which will be cell# of the replacement value
for the current value.
Starting with Cell#0, implement the following in a while loop:
1)
Check if the right child of Cell# is > (size-1):
If
true:
Check
if the left child of Cell# is > (size-1):
If yes:
End the while loop.
If no:
Set the value of minCell = Cell# of the left
child of Cell#
If false:
Find the
smaller of the values in left and right child of Cell#:
If
left of Cell# is the least, set minCell = Cell# of
the left child of Cell#
If
right of Cell# is the least, set minCell = Cell# of
the right child of Cell#
2)
If the loop has not ended:
If value in Cell# is less than value
in minCell
Swap the values in Cell#
and minCell
Set Cell# equal to minCell
Else
End the while loop
The array
after each iteration in the while loop:
Iteration #1:
Cell# = 0, minCell = 1. The values in these cells are swapped. The updated
value of Cell# = 1.
2 15 11 4 16 18
0 0 0 0
Iteration #2:
Cell# = 1, minCell = 3. The values in these cells are swapped. The updated
value of Cell# = 3.
2 4 11 15 16 18
0 0 0 0
The left Cell# of 3 is 7 and the
right Cell# of 3 is 8. As both of these values are > (size-1), the while
loop will terminate.
o
Step
#5: Return the variable, temp (=
1).
Additional
Methods:
· Build Min-Heap (or Heapify) O (n logn):
In this method, our goal is to build
a min-heap from an input array whose values do not satisfy the min-heap
property. I have implemented this method in the reference program.
· The Heap Sort algorithm O(n log n):
Heap sort is a sorting algorithm which follows
the following two steps to sort an input set of unsorted values in increasing
order (use a max-heap for decreasing order):
Step #1: Build a min-heap for the
input set of values.
Step #2: While the min-heap is not empty:
{
Return the root value
Delete the root
}