arrays - 检查具有 n 个元素的数组是否是最小堆的算法

Question

我正在尝试概述一种算法来确定我的数组是否是最小堆。是否有任何文件可以帮助我解决这个问题？我在 Apache 的网站上找到了它的一个函数，但它并没有准确地显示该函数是如何工作的；只是存在一个函数（BinaryHeap（boolean isMinHeap））。

Answer 1

维基百科的文章应该对您有所帮助。

以下是一些让您思考解决方案的问题：

1. 假设堆是最小堆，那么堆的根必须是什么？
2. 如果堆的根满足最小堆属性，如何确保根的子树也持有该属性？
3. 如果树的根没有孩子怎么办？是最小堆吗？

Answer 2

我认为这会奏效！

bool checkminheap(int arr[],root)
{
     if(root>=sizeof(arr)/sizeof(arr[0])-1)
         return 1;
     if(arr[root]>arr[2*root] || arr[root]>arr[2*root+1])  //check root is the smallest element
      return 0; 
    if(!checkminheap(arr,2*root))//check leftsubtree
      return 0;
    if(!checkminheap(arr,2*root+1))//check rightsubtree
      return 0;

     return 1;
}  

Answer 3

添加一个带有 java 泛型支持的详细解决方案，它相对更容易遵循。

public static <T extends Comparable<T>> boolean isMinHeap(T arr[], int rootIndex) {
  boolean isMaxH = true;
  int lChild = 2 * rootIndex + 1;
  int rChild = 2 * rootIndex + 2;

  // Nothing to compare here, as lChild itself is larger then arr length.
  if (lChild >= arr.length) {
    return true;
  }

  if (arr[rootIndex].compareTo(arr[lChild]) > 0) {
    return false;
  } else {
    isMaxH = isMaxH && isMinHeap(arr, lChild);
  }

  // rChild comparison not needed, return the current state of this root.
  if (rChild >= arr.length) {
    return isMaxH;
  }

  if (arr[rootIndex].compareTo(arr[rChild]) > 0) {
    return false;
  } else {
    isMaxH = isMaxH && isMinHeap(arr, rChild);
  }

  return isMaxH;
}