CSE205
Concepts of Computer Science and
Data Structure
Outline
•Heaps
•Heap Implementation
•Heap Sort
Heaps
•A heap is a complete binary tree in which each element is greater
than or equal to both of its children
•Two interesting extensions to a binary tree in a heap definition
–it is a complete tree
–the constraint on the relationship between elements
•As with binary search trees, there are many possible heap
configurations for a given set of elements
•Our definition above is really a maxheap
An Example Maxheap
Heaps
•A maxheap keeps the largest value of a set of elements readily
available
•Three primary operations for maxheaps (or the minheaps)
–add new element to the heap
–find the maximum/minimum value
–remove the maximum/minimum value
Adding an Element to a Heap
•To add an element to the heap, add the element as a leaf, keeping
the tree complete
•Then, move the element up toward the root, exchanging positions
with its parent, until the relationship among the elements is
appropriate
•This will guarantee that the resulting tree will conform to the heap
criteria
od
(ze)
Lt
()
Lats
Adding an Element to a Heap
Removing the Largest Element from a Heap
•We know that the largest element in a heap can be found at the
root
•Thus, we remove the root and reconstruct the heap from the two
disjoint sub-trees remaining
•Move the last leaf of the tree to be the new root of the tree
•Then, move it down the tree as needed (compare to the children)
until the relationships among the elements is appropriate
awa
Lis 21} 125
43
Es
Lis
}L2ty
2s)
Removing the Largest Element from a Heap
Outline
•Heaps
•Heap Implementation
•Heap Sort
Heap Implementation
•Our implementation commits at the interface level whether our
collection is a min-heap or max-heap
•The interface contains methods for
–adding a new element to the heap
–obtaining the highest value in the heap
–and removing the highest value in the heap
•Because a heap is a binary tree, our implementation can be based
on the LinkedBinaryTree class
•Please see the implementation in your book on page 710-716
Implementation Notes
•The LinkedMaxHeap class inherits the root reference from the
LinkedBinaryTree
•It also keeps track of the “last node” in the heap – the last leaf in
the complete tree
•The HeapNode class inherits the left and right reference
variables from the BTNode class
•A HeapNode object also keeps a reference to its parent object
(node), allowing us to move up the tree path
Implementation Notes
•Consider the process of adding
a new element as the “last
leaf” in the complete tree
•There is only one possible
position to add that leaf
•However, this position might
be on the level of current
leaves, or it could be the first
position of the next level if the
tree is currently full
Implementation Notes
•The add method of LinkedMaxHeap relies on two support methods
–getParentAdd: gets the parent of the new node to be added.
Starting at the last node in the tree, considers all possibilities, looking for the node
that will serve as the parent of the new node being added.
It looks up the tree until it is a left child of some node, or it finds the root. If it
reaches the root, then the new node is leftmost descendent of the root (and the new
leaf begins a new level). If it fails to reach the root, it looks for the leftmost
descendent of the right child.
–heapifyAdd: re-establishes the heap after the leaf is added.
Uses the parent references to move up the tree, swapping elements as needed. Note
that it only exchanges the elements, it does not move nodes
Outline
•Heaps
•Heap Implementation
•Heap Sort
Heap Sort
•Given the ordering property of a heap, it is natural to think of using
a heap to sort a list of numbers
•A heap sort sorts a set of elements by adding each one to a heap,
then removing them one at a time
•The largest element comes off the heap first, so the sequence will
be in descending order
•Similarly, a minheap can be used to sort the values in ascending
order
HeapSort
We can use a heap to sort
an array.
We use a max-heap.
The main idea:
• Build a heap from an array.
• With a max-heap, we can extract the root to get the largest value, and put it aside
(put it as the last
element of the array by swapping the root and the last element.)
• Then we continue to extract the next root (the second largest value, and put it as
the second last
element of the array.
• After doing this for n-1 times (where n is the number of elements in the initial
heap),
we will have a sorted (ascending order) array. To have a descending order array,
we can use a min-heap.
Since sorting an array means to sort any array, first we need to build a heap before
we start extracting
the roots.
Turning a tree into a max-heap. (Building a max-heap from an array)
For each node that has a child node, we call “fixHeap” or “Heapify” method.
We do this starting the node at , then we do for nodes
in the one level above. Then we keep going up to the node in the above level
until we call fixHeap on the root.
The fixHeap method:
---------------------------------------------------------------
Repeat the following until both children
are larger or we reach the bottom of the tree.
1. we compare the node and its children.
2. If at least one of the children is larger than the node,
then swap it with the larger children.
Else
DONE!
3. If it is not done, go back to the step 1, with the node’s new
location.
----------------------------------------------------------------
/ 2 1N−
� �
� �
Turning a tree into a max-heap. (Building a max-heap from an array)
First we call fixHeap on each node in the
second lowest level.
Then we call fixHeap on each node in the third
lowest level
Then we call fixHeap on the root.
Heap Sort summary:
(using a max-heap)
1. Build a heap from a given array.
1.1. For each node with at least one child node (i.e., not leaves),
starting with the ones in the lowest level and ending with the root (bottom-
up order),
call the fixHeap (Heapify) method:
1.1.1 Repeat the following until its child nodes are smaller or reach the
bottom of the heap:
Compare the node and its children.
If at least one child is larger than the node, then swap the node
with the larger child node.
Else, DONE.
2. Extract the root for n-1 times where n is the number of elements in the heap
(array).
for (int i=0; i < n-1; i++)
Extract the root and swap it with the element at the (n-1-i)-th position of the
array.
Adjust the tree so that the heap property holds for every extraction.
Worst case running time of Heap Sort: O(n log n)
27
12
10
22 13 7 33
80 24 31
Example: Building a max-
heap
27
12
10
22 31 7 33
80 24 13
27
12
10
80 31 7 33
22 24 13
swap
swap
swap
27
12
33
80 31 7 10
22 24 13
swap
Next page
80
12
33
27 31 7 10
22 24 13
swap
12
80
33
27 31 7 10
22 24 13
swap
31
80
33
27 12 7 10
22 24 13
swap
31
80
33
27 13 7 10
22 12 12
DONE!
Continuing from the previous page.
2
0
1
5
1
0
2
5
1
0
7
8
9
9
1
5
1
0
2
5
1
0
7
8
2
0
1
5
1
0
9
2
5
1
0
7
8
2
0
2
1
0
9
1
5
5
1
0
7
8
2
0
1
0
9
2
1
5
5
1
0
7
8
2
0
8
9
2
1
5
5
1
0
7
1
0
2
0
Exchange
A[1] & A[n] Heapify
Exchange
A[1] & A[n-1]
Heapify
Exchange
. . .
2
0
1
5
8
9
1
0
1
0
5
7
2
4
1
23
5 6 7
8 9
123456789
2 5 7 8 9 10 10 15 20
A
n
n-2
n-1 n-1 n n-1 n
n
n
(n = 9)
/** This class applies the heapsort algorithm to sort an array. */
public class HeapSorter
{
private int[] a;
// Constructs a heap sorter that sorts a given array.
// @param anArray an array of integers
public HeapSorter(int[] anArray)
{
a = anArray;
}
// Sorts the array managed by this heap sorter.
public void sort()
{
int n = a.length - 1;
//for each node that has at least one child node
for (int i = (n - 1) / 2; i >= 0; i--)
fixHeap(i, n);
while (n > 0)
{
swap(0, n);
n--;
fixHeap(0, n);
}
}
// Ensures the heap property for a subtree, provided its children already fulfill the heap
property.
// @param rootIndex the index of the subtree to be fixed
// @param lastIndex the last valid index of the tree that contains the subtree to be fixed
private void fixHeap(int rootIndex, int lastIndex)
{
int rootValue = a[rootIndex]; //Remove root
// Promote children while they are larger than the root
int index = rootIndex;
boolean more = true;
while (more)
{
int childIndex = getLeftChildIndex(index);
if (childIndex <= lastIndex)
{
// Use right child instead if it is larger
int rightChildIndex = getRightChildIndex(index);
if (rightChildIndex <= lastIndex && a[rightChildIndex] > a[childIndex])
{
childIndex = rightChildIndex;
}
if (a[childIndex] > rootValue)
{
// Promote child
a[index] = a[childIndex];
index = childIndex;
}
else
{
// Root value is larger than both children
more = false;
}
}
else
{
// No children
more = false;
}
}
// Store root value in vacant slot
a[index] = rootValue;
}
// Swaps two entries of the array.
// @param i the first position to swap
// @param j the second position to swap
private void swap(int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Returns the index of the left child.
// @param index the index of a node in this heap
// @return the index of the left child of the given node
private static int getLeftChildIndex(int index)
{
return 2 * index + 1;
}
// Returns the index of the right child.
// @param index the index of a node in this heap
// @return the index of the right child of the given
node
private static int getRightChildIndex(int index)
{
return 2 * index + 2;
}
}
Sorting Algorithm Comparisons
Time
Sort
Average
Best
Worst
Remarks
Bubble sort
O(n^2)
O(n^2)
O(n^2)
Sloooow
Selection Sort
O(n^2)
O(n^2)
O(n^2)
Even a perfectly sorted input requires
scanning the entire array
Insertion Sort
O(n^2)
O(n)
O(n^2)
In the best case (already sorted), every
insert requires constant time
Heap Sort
O(n*log(n))
O(n*log(n))
O(n*log(n))
By using input array as storage for the
heap, it is possible to achieve
constant space
Merge Sort
O(n*log(n))
O(n*log(n))
O(n*log(n))
On arrays, merge sort requires O(n) space;
on linked lists, merge sort requires
constant space
Quicksort
O(n*log(n))
O(n*log(n))
O(n^2)
Randomly picking a pivot value (or
shuffling the array prior to sorting)
can help avoid worst case scenarios
such as a perfectly sorted array.
