Table Of Contents
* 🤓 INTRODUCTION
* 👉🏻 ABOUT HEAP SORT ALGORITHM
* 👨🏻🏫 EXPLANATION
* 🛠 IMPLEMENTATION
* 👩🏻💻 CODE
* 🤔 COMPLEXITY
* 🙏 THANK YOU
🤓 INTRODUCTION
Welcome, hackers!🚀 A new week, new victories. I hope you are all having a great day. Today, we will explore another sorting algorithm - the Heap sorting algorithm.
Also, please feel free to connect with me via Twitter, Instagram or LinkedIn 👨🏻💻
👉🏻 ABOUT HEAP SORT ALGORITHM
The heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest level, which is filled from the left up to a point.
The heapsort algorithm uses the heap data structure, and it starts by using "BUILD-MAX-HEAP" to build a max-heap on the input array A[1..n], where n = A.length; Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap- and we can do so by simply decrementing A.heap-size-we observer that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call a function MAX-HEAPIFY-FUNCTION(A,1), which leaves a max-heap in A[1..n-1]. The heapsort repeats this process for the max-heap of size n-1 down to a heap of size 2.
I know, it sounds overwhelming. It also did to me when I first read it years ago. As matter of fact, since we talk about the data structures, I will commit some of my time preparing a blog series where we can explore the magical world of data structures 🧙🏻♂️; so consider it as an announcement for the upcoming blog series!
👨🏻🏫 EXPLANATION
Let represent the heap sort algorithm visually, while we try to sort the following array: [8, 4, 7, 1, 3, 5]
🛠 IMPLEMENTATION
👨🏻💻 CODE
Play with the code!🚀
🤔 COMPLEXITY
The complexity of the Heapsort algorithm is in the very best case Big O of n, in the worst case, the complexity of the heap sort is Big O of nlog2n.
🙏 THANK YOU FOR READING!
References:
School notes...
School books...
Khan Academy
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
☕ SUPPORT ME AND KEEP ME FOCUSED!
Have a nice time hacking! 😊
Top comments (0)