Heap-sort in Data Structure

A data structure known as a heap is used by the effective sorting algorithm heap-sort to organise elements in a nondecreasing order. In order to fill the sorted list, it first builds a heap from the input data and then repeatedly extracts the least or maximum element from the heap.
The Heap Data Structure
A heap is a binary tree that fits two requirements:
Complete Binary Tree: A “complete binary tree” is a heap with all levels filled, maybe save the final level, which is filled from left to right. This allows sequential array-based element storage at low cost.
Heap-Order Property: A min-heap’s parent nodes have values less than or equal to their progeny, according to heap-order. A max-heap’s parent nodes are worth more than their children. This assures the tree’s base always has the lowest (or highest) member.
The completeness of an n-item heap gives it O(log n) height. For heap operations to operate efficiently, this logarithmic height is essential.
Heap-Sort Algorithm
There are two primary stages to heap-sort:
Building the Heap: Constructing the Heap The group of n elements is first converted into a heap. The “bottom-up heap construction” approach, which begins with the provided elements and organises them to satisfy the heap property, can be used to accomplish this effectively. This stage involves downheap (or heapify) operations from the last non-leaf node to the root to ensure that every subtree follows heap-order. Bottom-up building can be completed in O(n) time if all n key-value pairs are supplied concurrently.
Extracting Elements (Sorting): Sorting and Extracting Sorting begins with heap construction. Maximum heaps have the largest element at the root. This element gets switched out for the heap’s final element. The new root, which was the previous final element, is then “sifted down” (using heapify or downheap) to restore the heap-order property once the heap’s size has been effectively decreased by one. The next largest element is moved to its sorted place in the array after this process is done n-1 times. By simply reordering elements within the original array, this step is frequently implemented “in-place,” requiring very little supplemental memory.
Running Time Analysis
These two stages are the main determinants of Heap-sort efficiency:
Phase 1 (Heap Construction): If key comparisons take O(1) time, then building a heap with n entries from the bottom up takes O(n) time. This is due to the fact that, in the bottom-up strategy, the total cost of all nodes comes to O(n), even though individual downheap operations can take O(log n) time.
Phase 2 (Extraction and Sorting): n-1 remove min (or remove max) operations are carried out in phase two, which is extraction and sorting. In each remove min action, the root is removed (O(1)), the final element is moved to the root, and a downheap operation is carried out, which takes time proportionate to the heap’s height. Each remove min operation takes O(log n) time since the heap’s height is O(log n). This step requires O(n log n) time because there are n such procedures.
When both phases are combined, the second phase dominates the entire worst-case running time of Heap-sort, yielding O(n log n) time. In the worst situation, this is thought to be ideal for sorting techniques that rely on comparison.
In contrast to alternative sorting algorithms:
- The worst-case performance of heap-sort is O(n log n), which is far better than O(n^2) techniques such as insertion-sort or selection-sort.
- In fact, Heap-sort can occasionally outperform Quick-sort and Merge-sort on bigger sequences, albeit their worst-case scenarios may be worse. Heap-sort is optimal in the worst-case scenario. The relative order of equal elements may not be maintained in a conventional heap-sort implementation because stability is not guaranteed.
Code Example (Python)
The two primary functions of a heap are heapify (sifting down) and upheap (sifting up). A downheap function can be used to construct the heapsort algorithm. This is a conceptual Python implementation of a max-heap sort, which repeatedly extracts the maximum and places it at the end to sort in ascending order.
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# Check if left child exists and is greater than root
if left < n and arr[largest] < arr[left]:
largest = left
# Check if right child exists and is greater than largest
if right < n and arr[largest] < arr[right]:
largest = right
# If root is not the largest, swap and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a maxheap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)
Output:
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]