Document Description

9/26/2011
Heap Sort
Heap Sort
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.
We represent heaps in level order, going from left to right. The array corresponding to the heap above is [25, 13, 17, 5, 8, 3].
The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child

Document Share

Document Tags

Document Transcript

Heap Sort
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 completelyfilled on all levels except possibly lowest.
We represent heaps in level order, going from left to right. The array corresponding to theheap above is [25, 13, 17, 5, 8, 3].
The root of the tree A[1] and given index
i
of a node, the indices of its parent, left child andright child can be computed
PARENT (
i
)return floor(
i
/2
LEFT (
i
)return 2
i
RIGHT (
i
)return 2
i
+ 1
Let's try these out on a heap to make sure we believe they are correct. Take this heap,
9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 1/13
which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child,we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate2 * 2 + 1 = 5. This takes us (again, correctly) to the 6. Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so wecalculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1,which takes us to the 20.
Heap Property
In a heap, for every node
i
other than the root, the value of a node is greater than or equal (atmost) to the value of its parent.
A[PARENT (
i
)] ≥
A[
i
]
Thus, the largest element in a heap is stored at the root.
Following is an example of Heap:
9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 2/13
By thedefinition of a heap, all the tree levels are completely filled except possibly for thelowest level, which is filled from the left up to a point. Clearly a heap of height
h
has theminimum number of elements when it has just one node at the lowest level. The levels abovethe lowest level form a complete binary tree of height
h
-1
and
2
h
-1
nodes. Hence theminimum number of nodes possible in a heap of height
h
is
2
h
. Clearly a heap of height
h
,has the maximum number of elements when its lowest level is completely filled. In this casethe heap is a complete binary tree of height
h
and hence has
2
h+1
-1
nodes.Following isnot a heap, because it only has the heap property - it is not a complete binarytree. Recall that to be complete, a binary tree has to fill up all of its levels with the possibleexception of the last one, which must be filled in from the left side.
Height of a node
We define the height of a node in a tree to be a number of edges on the longest simpledownward path from a node to a leaf.
Height of a tree
The number of edges on a simple downward path from a root to a leaf. Note that the heightof a tree with
n
node is
lg
n
which is (
lg
n
). This implies that an n-element heap hasheight
lg
n
In order to show this let the height of the
n
-element heap be
h
. From the bounds obtained on
9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 3/13
maximum and minimum number of elements in a heap, we get
2
h
≤
n
≤ 2
h+1
-1
Where n is the number of elements in a heap.
2
h
≤
n
≤ 2
h+1
Taking logarithms to the base 2
h
≤ lg
n
≤
h
+1
It follows that
h
=
lg
n
We known from above that largest element resides in root,
A[1]
. The natural question to ask is where in a heap might the smallest element resides? Consider any path from root of the treeto a leaf. Because of the heap property, as we follow that path, the elements are either decreasing or staying the same. If it happens to be the case that all elements in the heap aredistinct, then the above implies that the smallest is in a leaf of the tree. It could also be that anentire subtree of the heap is the smallest element or indeed that there is only one element inthe heap, which in the smallest element, so the smallest element is everywhere. Note thatanything below the smallest element must equal the smallest element, so in general, only entiresubtrees of the heap can contain the smallest element.
Inserting Element in the Heap
Suppose we have a heap as follows
9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 4/13

Similar documents

Search Related

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x