如何检查数组是否为最小堆？

Question

我有以下数组。如何检查包含n个元素的数组是否为最小堆?

- BeLambda

---

请参考此链接：http://stackoverflow.com/questions/4157159/algorithm-for-checking-if-an-array-with-n-elements-is-a-minimum-heap - Jees K Denny

你是否在寻找std::is_heap函数？ - Igor Tandetnik

节点i的子节点位于2i和2i+1。因此，验证a[2i] >= a[i]和a[2i+1] >= a[i]，因为这是堆属性：子节点至少与其父节点一样大。 - Gene

@Gene 对我来说，从末尾开始并确认对于所有 i > 1，都满足 a[i] >= a[i/2]，逐步递减 i 更容易。这样，您就不必创建两个潜在的子索引并检查它们是否均在边界内。 - pjs

Answer 1

由于您的索引从1开始（索引0包含0-为什么？），因此可以按以下方法确定给定节点子节点的索引：

• 假设给定节点的索引为i
• i的左子节点的索引：2i
• i的右子节点的索引：2i + 1

因此，对于每个节点，您可以轻松检查两个子节点是否都大于该节点本身。

- wookie919

---

有些人喜欢把根放在索引1处。他们说这是出于性能原因（在计算左子节点时可以消除一个额外的加法运算，在计算父节点时可以消除一个减法运算），但我已经进行了性能比较：没有实质性的区别。缺点是它会导致像C一样的语言程序员产生无法计数的围栏错误。我认为人们这样做的主要原因是因为Sedgewick在1983年写了一本算法书，他所有的例子都是用Pascal编写的，使用的都是基于1的数组。即使今天，对他的Pascal示例的C翻译也很普遍。 - Jim Mischel

Answer 2

is_heap 是一个很好的建议。你只需要使用适当的比较器即可。而且你甚至可以轻松地将其与迭代器一起使用，以实现基于1的索引：

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

int main()
{
    std::vector<int> v {0, 5, 9, 11, 14, 18, 19 };
    std::cout << std::is_heap(
      v.begin()+1, // off by 1
      v.end(),
      std::greater<int>() // std::less is used by default for max-heap
    );
}

- luk32

Answer 3

熟悉的广度优先搜索（BFS）也可以应用于检查树是否为最小/最大堆。

#include <iostream>
#include <queue>

int main() {
    int tree[] = {5, 9, 11, 14, 18, 19, 21, 33, 17, 27};
    int size = 10;
    std::queue <int> q;
    q.push(0);
    bool flag = true;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        int left = 2*x+1, right = 2*x+2;  // 0-based indexing used here
        if(left < size) {    // check if left child exists or not.
            q.push(left);
          // check value at parent is less than child or not.
            if(tree[x] > tree[left]) {
                flag = false;
                break;
            }
        }
        if(right < size) {   // check whether right child exists or not.
            q.push(right);
            if(tree[x] > tree[right]) {  // check value of parent less than child.
                flag = false;
                break;
            }
        }
    }
    if(flag)
        std::cout << "It is minimum heap.\n";
    else
        std::cout << "Not a minimum heap.\n";
    return 0;
}

这个想法与wookie919类似。

- Shubham