Heap Sort

In this method we will interpret thee array to be sorted as a binary tree, in a sequential representation of the binary tree we shall have

1.      The father node at location (i-2)/2 if is not equal to zero.

2.      The left child at location 2i+1.

3.      The right child at location 2i+2.

As the subscripts in C start from 0 to (MAXSIZE-1)

A heap is defined as an almost complete binary tree of n nodes such that the value of each node is less than or equal to the value of the father. In sequential representation of an almost complete binary tree of n nodes such that the value of each node is less than or equal to the value of the father. In sequential representation of an almost complete binary tree, we can write it as

                    K[ j ] < k[(i-2)/2] for 0 < (i-1)/2 < j< (n-1)

This implies that that root of the binary tree (i.e. the first array element) has the largest key in the heap. This type of heap is usually called descending heap or max heap, as the path from the root node to a terminal node forms an ordered list of elements arranged arranged in descending order.

             heap representation

We can also define as ascending heap as an almost complete binary tree in which the value of each node is greater than or equal to the value of its father. This implies that the root of the binary tree has the smallest elements of the heap. This type of heap is also called min heap.

A heap is very useful in implementing priority queues. The priority queue is a data structure in which the intrinsic ordering of the data items determines the result of its basic operations primarily queues can be classified into two types.

1.      Ascending priority queue.

2.      Descending priority queue.

An ascending priority queue can be defined as a group of elements to which new elements are inserted arbitrarily but only the smallest element is deleted from it. On the other hand a descending priority queue can be as a group of elements are inserted arbitrarily but only the largest element is deleted from it.

Heap as a Priority Queue

In this section you will be implementing the descending priority queue by making use of a descending heap. Let DPQ be an array of size k and is used to represent a descending heap.

Now we can implement the insertion operation on priority queue. Let us denote this operation as DPQ insert. This operation receives three parameters such as DPQ array, the parameter for insertion and deletion operation and element to be inserted. Thus the definition of DPQ insert for insertion is as

                        DPQ_insert (DPQ, k, addval)

After execution of this function the array DPQ becomes a heap of size k+1.

To insert an element we have to traverse the path from an empty position k to the position of the root and search the first element whether it is greater than or equal to addval. If the desired element is found then insert addval in its proper position. Since an element smaller than the addval is passed during the traversal it is necessary to shift one level in the tree down in order to accommodate the addval.

Sorting using a Heap

            A heap can be used to sort a set of elements. Let A an array of n elements which is used to represent a descending priority queue. The two main processing stages of a heap sort are creating a heap using DPQ insert operation and adjusting the heap as a result of deletion operation.

Efficiency of Heap sort

Let us consider the timing analysis of this heap sort. Since heap is an almost complete binary tree the worst case analysis is easier than the average case. In order to sort a given array elements we need to create a heap and then adjust it. This requires number of comparisons in the worst case is O (n log n). the worse case behavior of heap sort is for superior to quick sort.

Data Structure & Algorithms Assignment Help, Live Experts

Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.

ExpertsMind.com - Heap Sort Assignment Help, Heap Sort Homework Help, Heap Sort Assignment Tutors, Heap Sort Solutions, Heap Sort Answers, Sorting Assignment Tutors