如何构建最小和最大堆

数据结构在计算机编程中非常重要，可以快速有效地组织、管理和存储数据。数据结构对于任何开发人员来说都是其工具包中绝对必要的技能。

此篇文章重点关注堆，这是一种特殊的基于树的数据结构，它实现了完整的二叉树。

什么是堆？

堆是一种高级的基于树的数据结构，主要用于排序和实现优先级队列。它们是完全二叉树，具有以下特征：

• 除了叶节点（没有子节点的节点称为叶节点）之外，每个级别都已填充。
• 每个节点最多有 2 个子节点。
• 所有节点都尽可能远离左侧，这意味着每个子节点都位于其父节点的左侧。

堆使用完全二叉树来避免数组中出现漏洞。完全二叉树是每个节点最多有两个子节点的树，除了叶节点可以为空之外，所有级别的节点都是满的。堆是根据堆属性构建的，它将父节点键与其子节点键进行比较。

在本文的后面部分，我们将详细讨论基于最小堆属性构建的最小堆和基于最大堆属性构建的最大堆。

需要注意的是，堆并不总是排序的，它们遵循的关键条件是最大或最小元素放置在根节点（顶部）上，具体取决于它是最大堆还是最小堆。堆数据结构与堆内存不同。

堆的优点和缺点

优点：

• 垃圾收集在堆内存上运行以释放对象使用的内存。
• 堆很灵活，因为可以按任何顺序分配或删除内存。
• 变量可以全局访问。
• 它有助于找到最小和最大数字。

缺点：

• 与堆栈相比，堆需要更多的执行时间。
• 堆内存中的内存管理更加复杂，因为它是全局使用的。
• 堆通常需要更多时间来计算。

堆数据结构的应用

堆对于查找数组中的最小或最大元素非常有效，并且对于顺序统计和选择算法很有用。从堆中获取最小值/最大值的时间复杂度为O（1），（恒定时间复杂度）。

优先级队列是基于堆结构设计的。它需要氧O ( log ( n ) ) 有效地插入（insert()）和删除（delete()）优先级队列中每个元素的时间。

堆实现的优先级队列用于流行的算法，例如：

• 普利姆（Prim’s）算法
• 迪杰斯特拉算法
• 堆排序算法

堆中的基本操作

以下是实现堆数据结构时可能使用的基本操作：

• heapify：重新排列堆中的元素以保持堆属性。
• insert：将项目添加到堆中，同时保持其堆属性。
• delete：删除堆中的项目。
• extract：返回一个项目的值，然后将其从堆中删除。
• isEmpty： boolean，如果boolean为空则返回true，如果有节点则返回false。
• size：返回堆的大小。
• getMax()：返回堆中的最大值

如何构建最大堆

最大堆中的元素遵循最大堆属性。这意味着父节点的键始终大于两个子节点的键。要构建最大堆：

• 在堆的开头（根）创建一个新节点。
• 为其指定一个值。
• 将子节点的值与父节点的值进行比较。
• 如果父节点的值小于任一子节点的值（向左或向右），则交换节点。
• 重复此操作，直到最大元素位于根父节点（此时可以说堆属性成立）。

将新元素插入堆时也可以遵循这些步骤。这里的关键是，无论在最大堆上执行什么操作，都必须维护堆属性。

要移除/删除最大堆中的根节点：

• 删除根节点。
• 将最后一层的最后一个子节点移动到根。
• 将父节点与其子节点进行比较。
• 如果父节点的值小于子节点，则交换它们，并重复直到满足堆属性。

让我们看一下代码中的样子。我们将使用JAVAScript实现最大堆。

在 JavaScript 中实现最大堆

在我们开始构建最大堆之前，先看一下我们将实现的一些方法及其用途：

• _percolateUp()：将堆属性从子节点恢复到根节点。
• _maxHeapify()：将堆属性从特定节点恢复到叶节点。
• insert()：将给定值附加到堆数组并根据元素的堆属性重新排列元素。在每个新插入中，堆均匀增长，并且大小增加一。
• getMax()：返回堆（根节点）中的最大值，不修改堆。注意这里的时间复杂度是常数时间氧（1）欧（1 ）
• removeMax()：返回并删除堆中的最大值（想想pop()）。该函数的时间复杂度为O ( log ( n ) ) 。

如果堆大小大于一，它将最大值存储到变量中，将该值与最后一个叶子交换，然后从堆中删除最大值。

如果堆只有一个元素，则删除并返回该元素的值，最后一个条件是如果堆为空，则返回 null。

该__percolateUp()方法在每个父节点上递归调用，直到到达根。对于要定位在 max-heap 属性之后的每个节点，我们__maxHeapify()从堆底部开始在该数组的每个索引处调用该方法。

class maxHeap {
    constructor() {
        this.heap = [];
        this.elements = 0;
    };

    insert(val) {
        if (this.elements >= this.heap.length) {
            this.elements = this.elements + 1;
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };

    getMax() {
        if (this.elements !== 0)
            return this.heap[0];
        return null;
    };

    removeMax() {
        let max = this.heap[0];
        if (this.elements > 1) {
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__maxHeapify(0);
            return max
        } else if (this.elements === 1) {
            this.elements = this.elements - 1;
            return max;
        } else {
            return null;
        }
    };

    __percolateUp(index) {
        const parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] < this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };
    
    __maxHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let largest = index;
        if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
            largest = left
        }
        else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
            largest = right
        else if (largest !== index) {
            const tmp = this.heap[largest];
            this.heap[largest] = this.heap[index];
            this.heap[index] = tmp;
            this.__maxHeapify(largest);
        }
    };

    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__maxHeapify(i);
        }

    };
};
let heap = new maxHeap();

如何构建最小堆

直观上，我们可以说最小堆中的元素遵循最小堆属性，因为这与最大堆相反。父节点的键始终小于两个子节点的键。为了构建最小堆，我们：

• 在堆的末尾（最后一层）创建一个新的子节点。
• 将新键添加到该节点（将其附加到数组）。
• 向上移动子节点，直到到达根节点并且满足堆属性。

要移除/删除最小堆中的根节点：

• 删除根节点。
• 将最后一个子项的密钥移至 root。
• 将父节点与其子节点进行比较。
• 如果父节点的值大于子节点，则交换它们，并重复直到满足堆属性。

在 JavaScript 中实现最小堆

在我们开始构建最小堆之前，请注意它的实现与最大堆类似。minHeapify()恢复堆属性。getMin()返回堆（根节点）中的最小值，而不修改堆。并removeMin()删除最小值并返回它。

class minHeap {
    constructor() {
        this.heap = []
        this.elements = 0;
    };

    insert(val) {
        if (this.elements >== this.heap.length) {
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };
    
    getMin() {
        if (this.heap.length !== 0)
            return this.heap[0];
        return null;
    }

    removeMin() {
        const min = this.heap[0];
        if (this.elements > 1) {            
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__minHeapify(0);
            return min;
        } else if (this.elements == 1) {
            this.elements = this.elements - 1;
            return min;
        } else {
            return null;
        }
    };

    __percolateUp(index) {
        let parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] > this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };

    __minHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let smallest = index;
        if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
            smallest = left;
        }
        if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
            smallest = right;
        if (smallest !== index) {
            let tmp = this.heap[smallest];
            this.heap[smallest] = this.heap[index];
            this.heap[index] = tmp;
            this.__minHeapify(smallest);
        }
    }

    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__minHeapify(i)
        }
    }
};

let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);

console.log(heap.getMin()); //你应该得到-10

let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //使用数组中的元素构建这个堆
console.log(newheap.getMin()) //这里记录了 3

newheap.removeMin();

console.log(newheap.getMin())

堆进阶：将最大堆转换为最小堆

让我们通过实践挑战使我们的学习更进一步。我们的目标是将最大堆转换为最小堆。跟随我们的代码解决方案看看它是如何完成的。

问题描述：实现一个函数convertMax(maxHeap)，将二进制最大堆转换为二进制最小堆，其中maxHeap是 格式的数组maxHeap（即父级大于子级）。您的输出应该是转换后的数组。

输入示例：

maxHeap = [9,4,7,1,-2,6,5]

示例输出：

result = [-2,1,5,9,4,6,7]

function convertMax(maxHeap) {
    return maxHeap
}

上面的代码解决方案可以运行。我们可以将给定视为maxHeap一个规则的元素数组，并将其重新排序，以便它准确地表示最小堆。该函数通过在每个节点上convertMax()调用该函数，从最低父节点开始恢复所有节点上的堆属性。minHeapify()

构建堆的时间复杂度为O ( n )。对于这个问题也是如此。

function minHeapify(heap, index) {
    var left = index * 2;
    var right = (index * 2) + 1;
    var smallest = index;

    if ((heap.length > left) && (heap[smallest] > heap[left])) {
        smallest = left
    }
    if ((heap.length > right) && (heap[smallest] > heap[right]))
        smallest = right
    if (smallest != index) {
        var tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        minHeapify(heap, smallest)
    }
    return heap;
}

function convertMax(maxHeap) {
    for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap
}

var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))

常见的问题

以下是一些常见的挑战，有助于测试您对堆数据结构的了解。可能会在编码面试中看到以下问题：

• 将最大堆转换为最小堆
• 查找数组中 k 个最小元素
• 查找数组中第 k 个最大元素
• 检查给定数组是否代表最小堆
• 合并M个可变长度的排序列表
• 从每个给定列表中查找至少包含一个元素的最小范围

尝试解决这些问题，对堆数据结构会有更深入的了解！

总结

总结来说，构建最小堆和最大堆的步骤都是逐个插入元素，并通过与父节点的比较来调整元素的位置，以满足堆的性质。这样可以构建一个高效的数据结构，用于高效地插入、删除和访问优先级顺序的元素。