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:

image

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:

image

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

image

image

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]

image

1.Initialize the essentially complete binary tree with n nodes by placing keys in the order given and then heapify the tree.

image

image

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.

imageDeleting a key from heap

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.

image

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

image

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

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout