Scribd
Upload
224 views5 pages

Data Structures: Heap Sort

Heap sort is a sorting algorithm that uses a heap data structure. It works by first transforming the input array into a max-heap, where the root is greater than or equal to its children. It then repeatedly swaps the largest value (root) with the last element and sifts it down to maintain the heap property, sorting the array from largest to smallest. The steps are: 1) build a max-heap from the input array, 2) swap the root with the last element and reduce the heap size, 3) sift the new root down to maintain the heap, repeating until the heap size is 1.

Uploaded by

akash ravi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
224 views5 pages

Data Structures: Heap Sort

Heap sort is a sorting algorithm that uses a heap data structure. It works by first transforming the input array into a max-heap, where the root is greater than or equal to its children. It then repeatedly swaps the largest value (root) with the last element and sifts it down to maintain the heap property, sorting the array from largest to smallest. The steps are: 1) build a max-heap from the input array, 2) swap the root with the last element and reduce the heap size, 3) sift the new root down to maintain the heap, repeating until the heap size is 1.

Uploaded by

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

Data Structures

Home / My courses / BCA204A21T / Unit 2 - SEARCHING & SORTING - Heap Sort / HEAP SORT

HEAP SORT
Definition

Example

Algorithm - maxHeap

Definition: Heap Sort

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then,  

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types:

Min-Heap, where the value of the root node is less than or equal to either of its children.

Max-Heap, where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Steps to be followed for heap sort

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.

Step 3 − Compare the value of this child node with its parent.

Step 4 − If value of parent is less than child, then swap them.

Step 5 − Repeat step 3 & 4 until Heap property holds.

Example

◄ Program - Quick and Merge Sort Jump to... Unit 2 ►


Data Structures
Home / My courses / BCA204A21T / Unit 2 - SEARCHING & SORTING - Heap Sort / HEAP SORT

HEAP SORT
Definition

Example

Algorithm - maxHeap

Algorithm: maxHeap

procedure heapsort(a, count) is

    input: an unordered array a of length count

     (Build the heap in array a so that largest value is at the root)

    heapify(a, count)

     (The following loop maintains the invariants that a[0:end] is a heap and every element

     beyond end is greater than everything before it (so a[end:count] is in sorted order))

    end ← count - 1

    while end > 0 do

        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)

        swap(a[end], a[0])

        (the heap size is reduced by one)

        end ← end - 1

        (the swap ruined the heap property, so restore it)

        siftDown(a, 0, end)

Challenge Questions

◄ Program - Quick and Merge Sort Jump to... Unit 2 ►


Data Structures
Home / My courses / BCA204A21T / Unit 2 - SEARCHING & SORTING - Heap Sort / HEAP SORT

HEAP SORT
Definition

Example

Algorithm - maxHeap

Example

Input → 35   33   42   10   14   19   27   44   26   31

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:
Algorithm - maxHeap

◄ Program - Quick and Merge Sort Jump to... Unit 2 ►

You might also like