[go: up one dir, main page]
Scribd
Upload
393 views9 pages

Heap Sort

Heap Sort is an in-place sorting algorithm that works in two phases: (1) arranging the input elements into a max-heap data structure, and (2) removing the top element of the heap and placing it at the end of the sorted output array. The heap is reconstructed after each removal to maintain the heap property. A heap is a complete binary tree data structure where each node is greater than or equal to its children (max-heap) or less than or equal to its children (min-heap). To build a max-heap from an unsorted array, elements are compared to their parents and swapped if greater, bubbling up the largest elements to the root.

Uploaded by

Koteswara Rao L
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
393 views9 pages

Heap Sort

Heap Sort is an in-place sorting algorithm that works in two phases: (1) arranging the input elements into a max-heap data structure, and (2) removing the top element of the heap and placing it at the end of the sorted output array. The heap is reconstructed after each removal to maintain the heap property. A heap is a complete binary tree data structure where each node is greater than or equal to its children (max-heap) or less than or equal to its children (min-heap). To build a max-heap from an unsorted array, elements are compared to their parents and swapped if greater, bubbling up the largest elements to the root.

Uploaded by

Koteswara Rao L
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 9

Heap Sort

Heap Sort is one of the best sorting methods


being in-place and with no quadratic worst-case
scenarios.
Heap sort algorithm is divided into two basic parts :
1.Creating a Heap of the unsorted list.
2.Then a sorted array is created by repeatedly
removing the largest/smallest element from the
heap, and inserting it into the array.
The heap is reconstructed after each removal.

Heap is a special tree-based data structure,


that satisfies the following special heap
properties :
Shape Property : Heap data structure is
always a Complete Binary Tree, which means
all levels of the tree are fully filled.

Heap Property : All nodes are either [greater


than or equal to] or [less than or equal
to] each of its children.
If the parent nodes are greater than their
children, heap is called a MaxHeap(descending heap), and
if the parent nodes are smaller than their child
nodes, heap is called Min-Heap(ascending
heap) .

Building a heap
Given an unsorted array, the first step is to
build a heap(or max-heap) out of that array so
that elements of the array fulfils the heap
property.
To build a heap out of the given array, the
elements in the given array are considered
one by one.
If an element ARR[i] is greater than its parent,
which is stored at location (i-1)/2, then the
element is swapped with its parent.

The element is then compared with its new


parent and a swap occurs, if it is greater than
its parent.
This process continues until no more
swapping is needed, or we are at the root
node.

You might also like