Scribd
Upload
5 views18 pages

Heapsort Algorithm Explained

Heapsort is an efficient sorting algorithm that operates in-place and has a time complexity of O(n log n), combining the advantages of insertion sort and merge sort. It utilizes a binary heap data structure, which can be either a max-heap or a min-heap, to organize elements for sorting. The document also discusses the properties of heaps, the process of building a heap from an array, and the runtime complexities associated with heap operations.

Uploaded by

Nehal
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
5 views18 pages

Heapsort Algorithm Explained

Heapsort is an efficient sorting algorithm that operates in-place and has a time complexity of O(n log n), combining the advantages of insertion sort and merge sort. It utilizes a binary heap data structure, which can be either a max-heap or a min-heap, to organize elements for sorting. The document also discusses the properties of heaps, the process of building a heap from an array, and the runtime complexities associated with heap operations.

Uploaded by

Nehal
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

Heapsort

Paramita Koley
Heapsort
● In-place like insertion sort
● Runs in O(n log n) like merge sort
● Combines better attributes of both algorithms
Heap
(Binary) heap data structure is an array object which can be viewed as a nearly complete binary tree

Show a picture

Attributes: Heap_size

Root of the tree = A[1]


Root: A[1]
Max-heap and min-heap
Max-heap

Used in heap-sort

Min-heap

Used in priority queue


Heap data structure
● Height of a node: number of edges on the longest simple downward path from
that node to a leaf
● Height of a heap: height of the root of the heap

What is height of a heap with n elements?


Questions

1. Maximum and minimum numbers of elements in a heap of height h?


2. Show that in any subtree of a max-heap, the root of the subtree contains the
largest value occurring anywhere in that subtree
3. Where in a max-heap might the smallest element reside, assuming that all
elements are distinct?
4. At which levels in a max-heap might the kth largest element reside at max,
assuming that all elements are distinct?
5. Is an array that is sorted increasingly a min-heap or max-heap or none?
6. Show that for a nearly complete binary tree, the leaves are A [ floor(n/2 ) + 1:
n ].
Build heap from an array
● Max-heapify

Input: Array A, heap size n, index i

Assumes left and right subtrees are max-heaps but A [ i ] can be smaller than
any of its child

Returns a max-heap rooted at i


Max-heapify
Max-heapify
Run-time complexity

for initial operations

for recursion on subtree (Why?)

Final recurrence looks like

Solution:
Questions
1. A = <27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0>. Max-heapify (A, 3)
2. Design min-heapify subroutine along with run-time complexity
3. Effect of calling max-heapify ( A, i ) for i > [Link]-size/2?
4. Worst-case for max-heapify. Create a max-heap that causes worst-case
run-time and explain the run-time.
Building a heap ( Build-max-heap )
Run time of building a heap
Max-heapify = O(log n)

Number of nodes = O(n)

Total cost = O(n log n)


Run time of building a heap
Max-heapify for a node of height h = O(h)

Number of nodes with height h =


Questions
Why does loop index i in build-max-heap decrease from floor(n/2) to 1 rather than
increase from 1 to floor(n/2)?
Heapsort Algorithm
Heap sort

You might also like