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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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