Sorting algorithms: JavaScript - Heap Sort 🚀
Tags: javascript, webdev, programming, algorithms
Published: 2021-02-08 19:33:49

Table Of Contents
        * 🤓 [INTRODUCTION](#intro)
        * 👉🏻 [ABOUT HEAP SORT ALGORITHM](#heap)
        * 👨🏻‍🏫 [EXPLANATION](#explain)
        * 🛠 [IMPLEMENTATION](#implement)
        * 👩🏻‍💻 [CODE](#code)
        * 🤔 [COMPLEXITY](#complex)
        * 🙏 [THANK YOU](#thank-you)


## 🤓 INTRODUCTION <a name="intro"></a>

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](https://twitter.com/lazar_dev), [Instagram](https://www.instagram.com/codespressoweb/) or [LinkedIn](https://www.linkedin.com/in/lazar-stankovic-44a199177/) 👨🏻‍💻


## 👉🏻 ABOUT HEAP SORT ALGORITHM <a name="heap"></a>
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](https://media.giphy.com/media/BY8ORoRpnJDXeBNwxg/giphy.gif)

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 <a name="explain"></a>
Let represent the heap sort algorithm visually, while we try to sort the following array: [8, 4, 7, 1, 3, 5]

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xuqwumaeyhkxr605tx3q.png)


##🛠 IMPLEMENTATION <a name="implement"></a>

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/1jl1k8w25ydetn8564q9.png)


##👨🏻‍💻 CODE <a name="code"></a>
Play with the code!🚀
{% jsfiddle https://jsfiddle.net/codespresso/5v7rh63y/6/ js,result,html,css %}


##🤔 COMPLEXITY <a name="complex"></a>
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 nlog<sub>2</sub>n. 


# 🙏 THANK YOU FOR READING!<a name="thank-you"></a>
References:
School notes...
School books...
[Khan Academy](https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort)

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me! 

☕ SUPPORT ME AND KEEP ME FOCUSED!
<a href='https://ko-fi.com/Z8Z33D1HJ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://cdn.ko-fi.com/cdn/kofi4.png?v=2' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>

Have a nice time hacking! 😊