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

Number of leaf nodes in a complete binary tree, The number of leaf nodes in...

The number of leaf nodes in a complete binary tree of depth d is    2 d

Program to implementing stack using linked lists, include include i...

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

How to measure the algorithm efficiency, How to measure the algorithm's eff...

How to measure the algorithm's efficiency? It is logical to examine the algorithm's efficiency as a function of some parameter n showing the algorithm's input size. Instance

Define queue fifo ?, A queue is a particular type of collection or abstract...

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

Explain binary search tree, Binary search tree. A binary search tree is...

Binary search tree. A binary search tree is a binary tree that is either empty or in which every node having a key that satisfies the following conditions: - All keys (if an

Bayesian statistics question, Suppose that there is a Beta(2,2) prior distr...

Suppose that there is a Beta(2,2) prior distribution on the probability theta that a coin will yield a "head" when spun in a specified manner. The coin is independently spun 10 tim

What are the example of area subdivision method, Example of Area Subdivisio...

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

Explain about the doubly linked list with neat diagram, Problem 1. Expl...

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

Importance of object-oriented over java, Importance of Object-Oriented over...

Importance of Object-Oriented over java Java is basically based on OOP notions of classes and objects. Java uses a formal OOP type system that should be obeyed at compile-t

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