DEV Community

loading...
Cover image for Sorting algorithms: JavaScript - Heap Sort πŸš€

Sorting algorithms: JavaScript - Heap Sort πŸš€

codespresso profile image Codespresso ・3 min read

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.

Scott

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]

Alt Text

πŸ›  IMPLEMENTATION

Alt Text

πŸ‘¨πŸ»β€πŸ’» 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!
Buy Me a Coffee at ko-fi.com

Have a nice time hacking! 😊

Discussion (0)

pic
Editor guide