Heaps and Heap sort.
Heaps
Definition:
A heap is a binary tree with keys assigned to its nodes, provided the following two conditions are met:
i. Tree’s shape requirement: The binary tree is essentially complete, all its level are full except possibly the last level, where only some rightmost leaves may be missing.
ii. Parental dominance requirement: The key at each node is greater than or equal to the keys at its children.
Example:
Important properties of heap
1. There exists exactly one essentially complete binary tree with n nodes. Its height is
equal to └ log2n ┘
2. The root of a heap always contains its largest element
3. A node of a heap considered with all its descendents is also a heap.
4. A heap can be implemented as an array by recording its elements in the top-down, left-to-right fashion. Heap elements are stored in positions 1 through n of an array. In such representation:
a. The parental node keys will be in the first └ n/2 ┘ positions of the array, while the leaf keys will occupy the last ┌n/2┐ positions.
b. The children of a key in the array’s parental position i (1 ≤ i ≤ └ n/2 ┘ ) will be in position 2i and 2i +1, and, correspondingly the parent of a key in position i (2 ≤ i ≤ n) will be in position └ i/2 ┘
Example:
Heap construction
Construct heap for the list: 2, 9, 7, 6, 5, 8
There are two methods for heap construction:
1. Top-down construction: Constructs a heap by successive insertions of a new key into a previously constructed heap.
Insert 2 into empty tree
2. Bottom - up construction:
ALGORITHM HeapBottomUp(H[1…n])
//constructs a heap from the elements of a given array by bottom-up algorithm
//i/p: An array H[1…n] of orderable items
//o/p: A heap H[1…n]
1.Initialize the essentially complete binary tree with n nodes by placing keys in the order given and then heapify the tree.
Inserting a key into heap
Example: Insert a key 10 into the heap (9, 6, 8, 2, 6, 7)
Insert the new key as the last node in the heap, then heapify.
Example: Delete the root’s key from the heap (9, 8, 6, 2, 5, 1)
Solution:
MAXIMUM Key Deletion algorithm
Step 1: Exchange the root’s key with the last key K of the heap.
Step 2: Decrease the heap’s size by 1
Step 3: “Heapify” the smaller tree.
Heap sort
Description:
• Invented by J.W.J Williams
• It is a two stage algorithm that works as follows:
o Stage 1: (Heap construction): Construct a heap for a given array
o Stage 2: (maximum deletions): Apply the root-deletion operation n-1 times to the remaining heap
Example:
Sort the following lists by heap sort by using the array representation of heaps.
2, 9, 7, 6, 5, 8
Efficiency of heap sort:
Heap sort is an in place algorithm. Time required for heap construction + time required for maximum deletion
= O(n) + O(n log n)
= O(n log n)
Comments
Post a Comment