Heap Sort Visualization

What is Heap sort?

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.

Heap sort processes the elements by creating the min-heap or max-heap using the elements of the given array. Min heap or max heap represents the ordering of the array in which root element represents the minimum or maximum element of the array. At each step, the root element of the heap gets deleted and stored into the sorted array and the heap will again be heapified.

Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure. Like mergesort, heapsort has a running time of O(nlog⁡n),O(n\log n),O(nlogn), and like insertion sort, heapsort sorts in-place, so no extra space is needed during the sort.

What is a Heap?

Heap is a type of balanced binary tree data structure in which the root-node key is compared to its children, and the data is ordered as a result. Heaps are complex data structures that can be used for various tasks, including sorting and creating priority queues, or array elemets.

Complexity Analysis of Heap Sort algorithm

Heap Sort is one of the best sorting methods in place and with no quadratic worst-case running time. For this reason, most popular programming languages like C, C++, Java, and Python provide a robust implementation.

• Worst Case Time Complexity: O(n*log n)
• Best Case Time Complexity: O(n*log n)
• Average Time Complexity: O(n*log n)
• Space Complexity : O(1)

Heapsorting visualisation

Our program animation implementation tries to demonstrate how heaps are sorted using an algorithm. In general, you'll only need to use the heapsort method if your max or min heaps are evenly balanced. This algorithm, on the other hand, takes an array, places it in a max heap, and then sorts the items by picking the largest item, storing it at the bottom of the array, and so on.
Heapification and heap-based sorting are examples of heap visualisation in binary form.

Heapification

Definition algorithm: Rearrange a heap to preserve the heap's attribute that its key is greater (more or smaller) than or comparable to its keys. The term "heapify" refers to the procedure of converting a binary tree into a Heap data structure.

Binary Min-Max Heap Implementation

• Use an array to store the data.
• Start storing from index 1, not 0.
• For any given node at position i:
• Its Left Child is at [2*i] if available.
• Its Right Child is at [2*i+1] if available.
• Its Parent Node is at [i/2]if available.

Min Heap vs. Max Heap

Min and Max heaps are complete binary trees with a few unique characteristics.

• Min –Heap
  The value of the root node is the smallest.
  Each node's value is the same as or greater than that of its parent node.
• Max-Heap
  The value of the root node is the highest.
  Each node's value is the same as or less than the value of its parent node.

A min-max heap is a complete binary tree data structure that incorporates the advantages of both a min-heap and a max-heap, namely, constant time retrieval and logarithmic time removal of both the minimum and maximum entries in the heap.
Min Heap and Max Heap visualization is a simple method that uses a binary heap data structure to visually animate the processes.