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

Deletion from a red-black tree, Deletion in a RBT uses two main processes, ...

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

Data structures, I am looking for assignment help on the topic Data Structu...

I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

Explain arrays, Arrays :- To execute a stack we need a variable called top,...

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Total weight of minimum spanning tree, a) Run your program for α = 0.05, 0...

a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

Merging, Merging two sequence using CREW merge

Merging two sequence using CREW merge

Advantages of the last in first out method, Materials consumed are priced i...

Materials consumed are priced in a systematic and realistic manner. It is argued that current acquisition costs are incurred for the purpose of meeting current production and sales

Rl rotation - avl tree, Example: (Double left rotation while a new node is ...

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

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