HEAP DATA STRUCTURE

AND HEAP SORT

HEAP
A heap is a data structure that stores a
collection of objects (with keys), and
has the following properties:
 Complete Binary tree
 Heap Order

It is implemented as an array where

each node in the tree corresponds to
an element of the array.
HEAP
 The binary heap data structures is an array
that can be viewed as a complete binary
tree. Each node of the binary tree
corresponds to an element of the array. The
array is completely filled on all levels except
possibly lowest.
19

12 16

1 4 7

1 12 16 1 4 7
9
Array A
HEAP
 The root of the tree A[1] and given index i of
a node, the indices of its parent, left child
and right child can be computed

PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1
HEAP ORDER PROPERTY
 For every node v, other than the root, the
key stored in v is greater or equal (smaller or
equal for max heap) than the key stored in
the parent of v.
DEFINITION
 Max Heap
 Storedata in ascending order
 Has property of

A[Parent(i)] ≥ A[i]
 Min Heap
 Storedata in descending order
 Has property of

A[Parent(i)] ≤ A[i]
MAX HEAP EXAMPLE
19

12 16

1 4 7

1 12 16 1 4 7
9
Array A
MIN HEAP EXAMPLE
1

4 16

7 12 19

1 4 16 7 12 19

Array A
INSERTION
 Algorithm
1. Add the new element to the next available
position at the lowest level
2. Restore the max-heap property if violated
 General strategy is percolate up (or bubble up): if
the parent of the element is smaller than the
element, then interchange the parent and child.

OR

Restore the min-heap property if violated

 General strategy is percolate up (or bubble up): if
the parent of the element is larger than the
element, then interchange the parent and child.
 19 19

12 16 12 16

4 7 1 4 7 1
1
7
Insert 17
19

12 17
swap

1 4 7 1
6
Percolate up to maintain the
heap property
DELETION
 Delete max
 Copy the last number to the root ( overwrite the
maximum element stored there ).
 Restore the max heap property by percolate
down.

 Delete min
 Copy the last number to the root ( overwrite the
minimum element stored there ).
 Restore the min heap property by percolate
down.
HEAP SORT
A sorting algorithm that works by first organizing
the data to be sorted into a special type of
binary tree called a heap
PROCEDURES ON HEAP
 Heapify
 Build Heap

 Heap Sort
HEAPIFY
 Heapify picks the largest child key and compare it to
the parent key. If parent key is larger than heapify
quits, otherwise it swaps the parent key with the
largest child key. So that the parent is now becomes
larger than its children.
Heapify(A, i)
{
l  left(i)
r  right(i)
if l <= heapsize[A] and A[l] > A[i]
then largest l
else largest  i
if r <= heapsize[A] and A[r] > A[largest]
then largest  r
if largest != i
then swap A[i]  A[largest]
Heapify(A, largest)
}
BUILD HEAP
 We can use the procedure 'Heapify' in a bottom-up
fashion to convert an array A[1 . . n] into a heap.
Since the elements in the subarray A[n/2 +1 . . n] are
all leaves, the procedure BUILD_HEAP goes through
the remaining nodes of the tree and runs 'Heapify' on
each one. The bottom-up order of processing node
guarantees that the subtree rooted at children are
heap before 'Heapify' is run at their parent.

Buildheap(A)
{
heapsize[A] length[A]
for i |length[A]/2 //down to 1
do Heapify(A, i)
}
HEAP SORT ALGORITHM
 The heap sort algorithm starts by using procedure
BUILD-HEAP to build a heap on the input array A[1 . .
n]. Since the maximum element of the array stored at
the root A[1], it can be put into its correct final
position by exchanging it with A[n] (the last element
in A). If we now discard node n from the heap than the
remaining elements can be made into heap. Note that
the new element at the root may violate the heap
property. All that is needed to restore the heap
property.

Heapsort(A)
{
Buildheap(A)
for i  length[A] //down to 2
do swap A[1]  A[i]
heapsize[A]  heapsize[A] - 1
Heapify(A, 1)
Example: Convert the following array to a heap

16 4 7 1 12 19

Picture the array as a complete binary tree:

16

4 7

1 12 19
 16 16

4 7 4 19
swa
p

12 19 1 12 7
1

16 19
swa
p
12 19 12 16
swa
p

4 7 1 4 7
1
HEAP SORT
 The heapsort algorithm consists of two phases:
- build a heap from an arbitrary array
- use the heap to sort the data

 To sort the elements in the decreasing order, use a min heap

 To sort the elements in the increasing order, use a max heap

19

12 16

1 4 7
EXAMPLE OF HEAP SORT
Take out biggest
19

12 16
Move the last element
to the root

1 4 7

Sorted:
Array A

12 1 1 4 7 19
6
 7
swap
HEAPIFY()
12 16

1 4

Sorted:
Array A

7 12 1 1 4 19
6
 16

12 7

1 4

Sorted:
Array A

1 12 7 1 4 19
6
 Take out biggest
16
Move the last element
to the root
12 7

1 4

Sorted:
Array A

12 7 1 4 1 19
6
 4

12 7

Sorted:
Array A

4 12 7 1 1 19
6
 swap 4

HEAPIFY()
12 7

Sorted:
Array A

4 12 7 1 1 19
6
 12

4 7

Sorted:
Array A

12 4 7 1 1 19
6
 Take out biggest
12
Move the last
element to the
root 4 7

Sorted:
Array A

4 7 1 12 1 19
6
 1
swap

4 7

Sorted:
Array A

1 4 7 12 1 19
6
 7

4 1

Sorted:
Array A

7 4 1 12 1 19
6
 Take out biggest
7
Move the last
element to the
4 1 root

Sorted:
Array A

1 4 7 12 1 19
6
 swap 1

HEAPIFY()
4

Sorted:
Array A

4 1 7 12 1 19
6
 Take out biggest
Move the last 4
element to the
root
1

Sorted:
Array A

1 4 7 12 1 19
6
 Take out biggest
1

Sorted:
Array A

1 4 7 12 1 19
6
 Sorted:

1 4 7 12 16 19
TIME ANALYSIS
 Build Heap Algorithm will run in O(n) time
 There are n-1 calls to Heapify each call

requires O(log n) time

 Heap sort program combine Build Heap

program and Heapify, therefore it has the

running time of O(n log n) time
 Total time complexity: O(n log n)