Heap Sort in Python
Heap Sort: What is it?
We first need to comprehend some fundamental ideas about binary heaps to grasp how heap sort operates. Feel free to skip over these concepts and continue with the algorithm if you are already familiar with them.
A binary Heap is a tree-based data structure that satisfies the heap properties by having all of the tree nodes ordered in a certain way (that is, a specific parent-child relationship is followed throughout the tree).
A binary heap is a type of heap data structure where the tree is a full binary tree.
A binary tree is full if and only if:
- Except for the bottom level, all levels are full to capacity.
- The bottom level's nodes are all as far to the left as they may be.
- The final level might or might not be filled to capacity.
- A binary tree that has all of its nodes having either 0 or 2 children is said to be full.
Characteristics of a Binary Heap
Following are the characteristics of Heap Sorting:
- They are complete binary trees, which implies that all levels are completely filled (maybe with the exception of the last level), and the nodes in the last level are as far to the left as allowed. Arrays are a good data format for storing binary heaps because of this characteristic.
We can quickly determine a node's children's indices. The left child will therefore be located at index 2*i+1 for parent index i, and the right child will be found at index 2*i+2 (for indices that start with 0). Similar to this, the parent of a kid at index i can be discovered at index floor((i-1)/2). - The two main forms of heaps are maxing heaps and min heaps:
In a max heap, each child's value must be larger than or equal to the value of the corresponding node.
In a min heap, a parent's value is never more than or equal to the value of any of its children. - The element at the root of a max heap will always be the maximum. The root element in a min-heap will always be the smallest. The heap sort algorithm uses this attribute to sort an array using heaps.
Definition of a Heap Sort
The effective comparison-based sorting technique known as heap sort:
- Uses the supplied array to create a heap.
- Then uses the advantages of a heap to sort the array.
Heapify Technique
We'll think of the array as a complete binary tree before diving into the details of heap sort. Then, using a procedure known as heapification, we convert it into a maximum heap.
- The genius of heapification is revealed by the following:
- A binary tree is a MaxHeap if all of its subtrees are MaxHeaps in and of themselves.
Implementing this concept in one approach would be:
- Beginning at the base of the tree.
- As we ascend to the top, iterate through each node.
- Make that the node and all of its children create a valid max heap at each phase.
- If we are successful in doing that, after processing each node, the entire binary tree will have been converted into a valid MaxHeap.
- As none of the leaf nodes have children, omitting them would let this procedure run more efficiently:
- Go to the second-bottommost node on the right that has any children.
- Make sure that the node on the right creates a MaxHeap with its descendants by processing it.
- Repeat the operation by moving the node to its left.
We leap to the rightmost node of the level above it at the level's conclusion.
By going on to the top of the rightmost at one level, we reach the top most point, the root node of the binary tree, so that all the leaf and its children have been arranged so that it becomes the max heap.
Let's examine this more closely:
Step 1: Compare the node's value to the child nodes' values. Do nothing if the parent's value exceeds the child nodes' values.
Step 2: Swap the values of the parent and child nodes if the value of a child node exceeds that of the parent node.
Step 3: Replace the parent's value with the child's value which has the greater value between the two children (if both child nodes have values higher than the parent's).
We now repeat steps 1, 2, and 3 for the child node that received an update.
Recursion:
This is a recursive approach if that sounds familiar. Up until the point where the child node is either a leaf or has children, each of whose values is lower, we keep running this method recursively for the child nodes that got updated.
Traversal from Bottom to Top:
You might have been curious as to why we chose to travel bottom to top rather than top to bottom. This is due to the fact that steps 1-3 for heapifying a node only function if the child nodes are already heaped.
Max/Min Heap Formation
A max heap is entirely built at the conclusion of this procedure. We can also use this condition to generate a min heap by just changing it to "parent value should be <= each of its children's values" (swap values if the condition isn't met).
Uses of Heap Sort
Because quicksort and merge sort are more effective in real-world situations, heap sort is rarely used. We frequently utilize heaps to sort almost-sorted arrays, find the largest or smallest entries in an array, and other issues.
Heap sort has a variety of important uses, such as:
- placing priority queues into practice
- security measures
- Embedded Systems (for example, Linux Kernel).
Heap Sort: How does it Operate?
We will now explore using the heap to sort the array after learning how to generate a heap from an array using the heapify function.
After a heap is created using the heapify method, it is sorted using:
- The heap array's size is decreased by one, and the array's root element is switched with its final element. It is equivalent to adding the bottommost and rightmost leaf before removing the root (in heap representation).
- Reheapification, or restoring heap attributes after each deletion, requires that we only use the heapify technique on the root node. At the start of the procedure, the subtree heaps will still have all of their original heap characteristics.
The following steps should be repeated until the array's elements are all sorted:
- root removal
- storage in the heap's highest index position, and
- heap length reduction.
This procedure will sort the array in ascending order on a maximum heap.
This procedure sorts in decreasing order on a minimum heap.
Algorithm for Heap Sort
The heap sort algorithm is as follows:
Step 1: Create a heap. Utilizing the input data, create a heap. Create a maximum heap for increasing order sorting and a minimum heap for decreasing order sorting.
Step 2: Create a heap. Utilizing the input data, Switch the root. Replace the last item in a heap with the root element.
Step 3: Reduce the heap. Reduce the heap by 1.
Step 4: Re-Heapify . Call heapify on the root node to heapify the remaining items into a heap of the new heap size.
Step 5: Call recursively . As long as the heap size is more than 2, repeat steps 2, 3, and 4.
Always binary heaps seen and implemented using arrays, because An array is a faster and simpler way to store and access data than a more complex data structure. Using standard library methods for common data structure operations, such as the push() and pop() methods for a stack, is one of the key benefits of using more complicated data structures.
However, we can still simply conduct any operations that are important to the tree by maintaining a complete binary tree in an array. We can find the left child, right child, parent node, root, and last element of a tree using straightforward arithmetic operations on the index of the current node or the variable retaining the tree's size.
Program for Heap Sort:
def heapsort(alist):
build_max_heap(alist)
for i in range(len(alist) - 1, 0, -1):
alist[0], alist[i] = alist[i], alist[0]
max_heapify(alist, index=0, size=i)
def parent(i):
return (i - 1)//2
def left(i):
return 2*i + 1
def right(i):
return 2*i + 2
def build_max_heap(alist):
length = len(alist)
start = parent(length - 1)
while start >= 0:
max_heapify(alist, index=start, size=length)
start = start - 1
def max_heapify(alist, index, size):
l = left(index)
r = right(index)
if (l < size and a list[l] > alist[index]):
largest = l
else:
largest = index
if (r < size and a list[r] > alist[largest]):
largest = r
if (largest != index):
alist[largest], alist[index] = alist[index], alist[largest]
max_heapify(alist, largest, size)
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in list]
heapsort(alist)
print('Sorted list: ', end='')
print(list)
Output:
Enter the last numbers of to sort: 2 3 1 6 5 4
Sorted list is : 1 2 3 4 5 6 .
Advantages of the Heap Sort
Following are the advantages of Heap Sorting:
- No worst-case quadratic runtime.
- It performs sorting with O(1) space complexity and is an in-place sorting algorithm.
- It has a better worst-case runtime complexity than quicksort — O (nlog n).
- For both quick sort and heap sort, the best-case complexity is O(nlog n).
- It doesn't need additional space, unlike merge sort.
- The complexity is not compromised by the incoming data being totally or almost sorted.
- Merge sort and quicksort both have the same average-case complexity.
Disadvantages of Heap Sort
Following are the disadvantages of Heap Sorting:
- Since actions on the heap might change the relative order of items with equal keys, heap sort is often not reliable. Usually, the sorting algorithm is unstable.
- If the input array is huge and cannot fit into the memory and splitting the array is quicker than maintaining the heap, heap sort is not an option.
- The ideal option in these circumstances is a merge sort or bucket sort, where different elements of the array can be handled concurrently and individually.