JavaScript 实现堆排序的可视化

图形用户界面(GUI) 比程序更容易理解。在这篇文章中，我们将使用JavaScript来可视化堆排序。我们将看到如何将数组首先转换为最大堆，然后获取最终排序后的数组。我们还将可视化堆排序的时间复杂度。

参考:

堆排序
JavaScript中的异步函数

方法:

首先，我们将使用Math.random()函数生成一个随机数组。
使用不同的颜色来指示正在对比、排序和未排序的元素。
由于算法执行非常快，所以使用setTimeout()函数来减慢过程。
按下 “Ctrl+R” 键可以生成新的数组。
使用HeapSort()函数和Heapify()函数来执行排序。

示例: 在这个示例中，我们将使用上述方法来可视化堆排序。

JavaScript 实现堆排序的可视化

下面是可视化堆排序算法的程序。

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: 上述文件中使用的“style.css”文件的内容如下。

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: 下面是用于上面HTML代码的“ script.js ”文件的内容。

JavaScript代码

let container = document.getElementById("array");
 
// Function to generate the array of blocks
function 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 indexes
let 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 function
async 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 function
async 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 function
generatearray();
// Calling generate_idx function
generate_idx();
// Calling HeapSort function
HeapSort(20);

输出：

JavaScript 实现堆排序的可视化