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 where the value in every node is 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 (similar to how we navigated the
binary search trees last year).
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
}