A sorting algorithm is used to rearrange an array or a list of elements. In previous sections we have covered Bubble sort, Selection sort, Insertion sort, Merge sort, and Quick sort. Heap sort algorithm is one of the important sorting algorithms in data structures. So In this section, we’re going to see the complete working of heap data structure and then see the heap sort algorithm in python along with its time complexity and some features.
Before diving deep into understanding the sorting algorithm you must have some knowledge about heap data structure because heap sort builds a heap from the given array and then utilize that heap to sort the array further. So we will be covering some other sub-topics under this section.
What you’ll learn?
- Heap: Array representation of Binary Tree
- Complete Binary Tree vs Full Binary Tree
- Heap data structure: Max-heap and Min-Heap
- Insert operation in max-heap with example
- Delete operation in max-heap with example
If you know all the topics mentioned above, you can skip this part of the heap sort algorithm and can directly go to Part-2 of heap sort. Unless you know these things it’s difficult to directly jump onto heap sort.
Heap sort algorithm: Array Representation of Binary Tree
First let’s see the representation of a binary tree using an array. Here we have an example. This is a binary tree shown below. And its array representation. Now here indexing of the array starts from 1 but this is just theoretical. When you want to program you can start with 0 index. Tree elements are stored in an array so how they’re stored? For storing a binary tree we have to take care of 2 things. First, we have to store all the elements. Second, the relationship between them ( who is the parent, who’s the left child or right child ). Now let’s see how we preserve them in an array.
As you can see in the image elements are filled in the array level by level. And the relationship is formed by using some formulas. If any node is at index i then its left child is at 2*i, its right child is at 2*i +1 and it’s parent is at floor value of i/2. Let’s verify this. Take B, B is at index 2, it’s left child which is D must be at 2*i that is 4 and D is at 4, Right!. Now, it’s right child which is E must be at 2*i + 1 that is 5 and yes E is at 5. Its parent must be at floor of i / 2 which is 1 and yes A is at 1.
Note: Just fill the elements level by level, it will follow the formula automatically.
Complete Binary Tree vs Full Binary Tree
Full Binary Tree: When a tree has a maximum no. of elements having height h, it is known as a full binary tree. If you want to add any element then the height will increase.
Complete Binary Tree: If you represent a binary tree in an array then there should not be any empty gap in between the elements.
What is a Heap Data Structure?
Well, A heap is a specialized tree-based data structure which is essentially follows two properties. First, it is a complete binary tree. That means it will always have fully filled levels. Second, it satisfies the heap property.
Heap Data Structure Property: We always have a special arrangement of values in the nodes of the heap. Value in the parent node is either greater or equal to the values in its children nodes, known as max-heap. And, if the value in the parent node is either smaller or equal to the values in its children nodes, it is known as min-heap. See max-heap example and min-heap example images for better understanding.
Insert operation in Max-Heap: Heap Data Structure
As we saw we have two types of heap, max-heap, and min-heap. So, whatever we have to learn we’ll learn upon one type and the same thing applies on the next heap also. Now, we will learn how to insert and delete an element in max-heap. First, let us look at insert operation in a max-heap.
So we have a max-heap and its array representation. Suppose, you want to insert an element 60 in this max-heap. See where 60 should come. Now, root should have the largest element because of it’s a max-heap. And therefore, 60 should come at the root node. Now, don’t just directly put 60 at the root and shift all other elements, that’s wrong. What we will do here is we first place 60 at the last free space of the array. In tree representation, it will be the left child of 15. Now, just see the tree carefully. Is it a max-heap? No! Because every node should have a value greater than all its descendants. Now we adjust the elements.
We make it a heap. How? Compare the new node with its parent if the new node is greater than its parent node, swap them. So here, first we compare 60 with 15, and since 60 is greater it will go up and 15 will come down. Again, compare it with its parent that is 30, 60 is greater than 30 also, so we swap them also. At last 60 is compared with 50 and it will go up. So, 60 is compared with all its ancestors and it will reach its right place as shown below.
Time complexity of Insertion
So, this is insertion. We have inserted only one element in a max-heap. Now, let’s do a little bit of analysis. How much time it has taken? It has taken the time equal to the no. of swaps. So, maximum how many swaps it will take? That depends on the height of the tree. Therefore the time taken by the element to insert in a max-heap is O(logn).
The time taken by the insertion in a max-heap is O(logn).
If suppose the inserted element was not 60, it was 6 then we will not do any swaps and it will be inserted in constant time. So, we can say the insertion takes O(1) in best case scenario. And, it takes O(logn) in worst case.
To learn about the working of a heap sort algorithm please read Part-2 of the heap sort algorithm.
Check this video for more:
Credits to nETSETOS
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies! If you have any query feel free to ask in the comment section.
Happy Coding!
You may also read
Introduction to Searching Algorithms: Linear Search Algorithm
Bubble Sort Algorithm In Data Structures & Algorithms using Python
Merge Sort Algorithm in Python
Sorting Algorithms and Searching Algorithms in Python
Shutdown Computer with Voice in Python
