Heap sort, Data Structure & Algorithms

Assignment Help:

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree.

1345_Heap Sort.png

Figure: A Binary Tree

A complete binary tree is said to assure the 'heap condition' if the key of each node is greater than or equal to the key in its children. Therefore the root node will have the biggest key value.

Trees can be represented such as arrays, by first numbering the nodes (beginning from the root) from left to right. Then the key values of the nodes are assigned to array positions whose index is specified by the number of the node. For example, the corresponding array is depicted in Figure

444_Heap Sort.png

                                  Figure: Array for the binary tree of figure

The relationships of a node can also be found out from this array representation. If a node is at position of j, its children will be at positions 2j & 2j + 1. Its parent will be at position +J/2+.

Assume the node M. It is at position 5. Therefore, its parent node is at position

5/2+ = 2 that means the parent is R. Its children are at positions 2 × 5 & (2 × 5) + 1, that means 10 + 11 respectively that means E & I are its children.

A Heap is a complete binary tree, wherein each node satisfies the heap condition, represented as an array.

Now we will study the operations possible over a heap and see how these can be combined to produce a sorting algorithm.

The operations on a heap work into 2 steps.

1. The needed node is inserted/deleted/or replaced.

2. The above operation may cause violation of the heap condition thus the heap is traversed and modified to rectify any such kind of violations.

Examples: Assume the insertion of a node R in the heap 1.

1. Initially R is added as the right child of J & given the number 13.

2. However, R > J. hence, the heap condition is violated.

3. Move R up to position six & move J down to position thirteen.

4. R > P. thus, the heap condition is violated still.

5. Swap R & P.

4. Now the heap condition is satisfied by all nodes to get the heap of Figure

629_Heap Sort1.png

624_Heap Sort2.png

Figure: A Heap

This algorithm is guaranteed to sort n elements within (n log2n) time.

First we will see two methods of heap construction and then elimination in order from the heap to sort the list.

1. Top down heap construction

           • Add items into an initially empty heap, satisfying the heap condition at all steps.

2. Bottom up heap construction

            • Build a heap along the items in the order presented.

            • From the right most nodes modify to satisfy the heap condition. We will reveal this with an example.

 Example: construct a heap of the following using top down approach for heap construction.

                                        PROFESSIONAL

Figure illustrates different steps of the top down construction of the heap.

888_Heap Sort3.png

Figure: Heap Sort (Top down Construction)

Example: The input file is (2,3,81,64,4,25,36,16,9, 49). While the file is interpreted as a binary tree, it results in Figure. Another Figure shows the heap.

666_Heap Sort4.png

Figure: A Binary tree                   Figure: Heap of figure

Given figure illustrates several steps of the heap of above Figure as the sorting takes place.


Related Discussions:- Heap sort

Explain the arrays in ruby, Explain the Arrays in Ruby Ruby arrays are ...

Explain the Arrays in Ruby Ruby arrays are dynamic arrays which expand automatically whenever a value is stored in a location beyond current end of the array. To the programmer

Er diagram, Ask queConsider the following functional dependencies: Applican...

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O

Explain the term group support system, (a) Explain the term Group Support S...

(a) Explain the term Group Support System and elaborate on how it can improve groupwork. (b) Briefly explain three advantages of simulation. (c) Explain with the help of a

Evaluation of arithmetic expressions, Stacks are often used in evaluation o...

Stacks are often used in evaluation of arithmetic expressions. An arithmetic expression contains operands & operators. Polish notations are evaluated through stacks. Conversions of

Explain merge sort, Merge sort: Merge sort is a sorting algorithm that ...

Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

Dynamic memory management, How memory is freed using Boundary tag method in...

How memory is freed using Boundary tag method in the context of Dynamic memory management? Boundary Tag Method to free Memory To delete an arbitrary block from the free li

Determine about the push operation, Determine about the push operation ...

Determine about the push operation A Container may or may not be accessible by keys, so it can't make assumptions about element retrieval methods (for example, it cannot have a

Pseudo code, since the gregorian calendar was introduced in 1752,a leap yea...

since the gregorian calendar was introduced in 1752,a leap year occurs every 4 years.you are to write a pseudo code to find out whether a year is a leap year.your progrm should dis

Abstract Data Types, A useful tool which is used for specifying the logical...

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

What are the dynamic arrays, What are the Dynamic arrays Dynamic arrays...

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd