DEV Community

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

Posted on

6 1

Sorting algorithms: JavaScript - Heap Sort πŸš€

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! 😊

Heroku

Deliver your unique apps, your own way.

Heroku tackles the toil β€” patching and upgrading, 24/7 ops and security, build systems, failovers, and more. Stay focused on building great data-driven applications.

Learn More

Top comments (0)

Image of Stellar post

Check out Episode 1: How a Hackathon Project Became a Web3 Startup πŸš€

Ever wondered what it takes to build a web3 startup from scratch? In the Stellar Dev Diaries series, we follow the journey of a team of developers building on the Stellar Network as they go from hackathon win to getting funded and launching on mainnet.

Read more

πŸ‘‹ Kindness is contagious

Value this insightful article and join the thriving DEV Community. Developers of every skill level are encouraged to contribute and expand our collective knowledge.

A simple β€œthank you” can uplift someone’s spirits. Leave your appreciation in the comments!

On DEV, exchanging expertise lightens our path and reinforces our bonds. Enjoyed the read? A quick note of thanks to the author means a lot.

Okay