GUI(Graphical User Interface) helps in better understanding than programs. In this article, we will visualize Heap Sort using JavaScript. We will see how the array is first converted into Maxheap and then how we get the final sorted array. We will also visualize the time complexity of Heap Sort.
Refer:
Approach:
- First, we will generate a random array using Math.random() function.
- Different colors are used to indicate which elements are being compared, sorted, and unsorted.
- Since the algorithm performs the operation very fast, the setTimeout() function has been used to slow down the process.
- New array can be generated by pressing the “Ctrl+R” key.
- The sorting is performed using HeapSort() function using Heapify() function.
Example: In this example, we will see the visualization of Heap Sort by using the above approach.
Before Sorting
After Sorting
Below is the program to visualize the Heap Sort algorithm.
index.html
HTML
<!DOCTYPE html><html lang="en"><head> <link rel="stylesheet" href="style.css" /></head><body> <br /> <p class="header">Heap Sort</p> <div id="array"></div> <div id="count"></div> <script src="script.js"></script></body></html> |
style.css: The following is the content for “style.css” used in the above file.
CSS
* { margin: 0px; padding: 0px; box-sizing: border-box;}.header { font-size: 20px; text-align: center;}#array { background-color: white; height: 270px; width: 598px; margin: auto; position: relative; margin-top: 64px;}.block { width: 28px; background-color: #6b5b95; position: absolute; bottom: 0px; transition: 0.2s all ease;}.block_id { position: absolute; color: black; margin-top: -20px; width: 100%; text-align: center;}.block_id2 { position: absolute; color: black; margin-top: 22px; width: 100%; text-align: center;}.block2 { width: 28px; background-color: darkgray; position: absolute; transition: 0.2s all ease;}.block_id3 { position: absolute; color: black; margin-top: 1px; width: 100%; text-align: center;}#count { height: 20px; width: 598px; margin: auto;} |
script.js: The following is the content for “script.js” file used in the above HTML code.
Javascript
let container = document.getElementById("array");// Function to generate the array of blocksfunction generatearray() { for (let i = 0; i < 20; i++) { // Return a value from 1 to 100 (both inclusive) let value = Math.ceil(Math.random() * 100); // Creating element div let array_ele = document.createElement("div"); // Adding class 'block' to div array_ele.classList.add("block"); // Adding style to div array_ele.style.height = `${value * 3}px`; array_ele.style.transform = `translate(${i * 30}px)`; // Creating label element for displaying // size of particular block let array_ele_label = document.createElement("label"); array_ele_label.classList.add("block_id"); array_ele_label.innerText = value; // Appending created elements to index.html array_ele.appendChild(array_ele_label); container.appendChild(array_ele); }}// Function to generate the indexeslet count_container = document.getElementById("count");function generate_idx() { for (let i = 0; i < 20; i++) { // Creating element div let array_ele2 = document.createElement("div"); // Adding class 'block2' to div array_ele2.classList.add("block2"); // Adding style to div array_ele2.style.height = `${20}px`; array_ele2.style.transform = `translate(${i * 30}px)`; // Giving indexes let array_ele_label2 = document.createElement("label"); array_ele_label2.classList.add("block_id3"); array_ele_label2.innerText = i; // Appending created elements to index.html array_ele2.appendChild(array_ele_label2); count_container.appendChild(array_ele2); }}// Asynchronous Heapify functionasync function Heapify(n, i) { let blocks = document.querySelectorAll(".block"); let largest = i; // Initialize largest as root let l = 2 * i + 1; // left = 2*i + 1 let r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if ( l < n && Number(blocks[l].childNodes[0].innerHTML) > Number(blocks[largest].childNodes[0].innerHTML) ) largest = l; // If right child is larger than largest so far if ( r < n && Number(blocks[r].childNodes[0].innerHTML) > Number(blocks[largest].childNodes[0].innerHTML) ) largest = r; // If largest is not root if (largest != i) { let temp1 = blocks[i].style.height; let temp2 = blocks[i].childNodes[0].innerText; blocks[i].style.height = blocks[largest].style.height; blocks[largest].style.height = temp1; blocks[i].childNodes[0].innerText = blocks[largest].childNodes[0].innerText; blocks[largest].childNodes[0].innerText = temp2; await new Promise((resolve) => setTimeout(() => { resolve(); }, 250) ); // Recursively Hapify the affected sub-tree await Heapify(n, largest); }}// Asynchronous HeapSort functionasync function HeapSort(n) { let blocks = document.querySelectorAll(".block"); // Build heap (rearrange array) for (let i = n / 2 - 1; i >= 0; i--) { await Heapify(n, i); } // One by one extract an element from heap for (let i = n - 1; i > 0; i--) { // Move current root to end let temp1 = blocks[i].style.height; let temp2 = blocks[i].childNodes[0].innerText; blocks[i].style.height = blocks[0].style.height; blocks[0].style.height = temp1; blocks[i].childNodes[0].innerText = blocks[0].childNodes[0].innerText; blocks[0].childNodes[0].innerText = temp2; await new Promise((resolve) => setTimeout(() => { resolve(); }, 250) ); // Call max Heapify on the reduced heap await Heapify(i, 0); }}// Calling generatearray functiongeneratearray();// Calling generate_idx functiongenerate_idx();// Calling HeapSort functionHeapSort(20); |
Output:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
