Home | | Object Oriented Programming and Data Structures | Heap operations: algorithms, Heap Sort

Chapter: Object Oriented Programming and Data Structure : Linear Data Structures

Heap operations: algorithms, Heap Sort

Explain, with example the basic heap operations and write the algorithms for the same. Heap Sort

Explain, with example the basic heap operations and write the algorithms for the same. Heap Sort

 

Heap sort operates by first converting the list in to a heap tree. Heap tree is a binary tree in which each node has a value greater than both its children (if any). It uses a process called "adjust to accomplish its task (building a heap tree) whenever a value is larger than its parent.

The time complexity of heap sort is O(nlogn). Algorithm:

1. Construct a binary tree

The root node corresponds to Data[0].

 

  If we consider the index associated with a particular node to be i, then the left child of this node corresponds to the element with index 2*i+1 and the right child corresponds to the element with index 2*i+2. If any or both of these elements do not exist in the array, then the corresponding child node does not exist either.

 

2. Construct the heap tree from initial binary tree using "adjust" process.

 

3. Sort by swapping the root value with the lowest, right most value and deleting the lowest, right most value and inserting the deleted value in the array in it proper position.

Example: Sort the following list using heap sort algorithm.

5        8        2        4        1        3        9        7        6        0



Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Object Oriented Programming and Data Structure : Linear Data Structures : Heap operations: algorithms, Heap Sort |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.