Алгоритм проверки, является ли массив с n-элементами минимальной кучей

Question

Я пытаюсь обрисовать алгоритм, чтобы определить, является ли мой массив минимальной кучей.Есть ли какая-нибудь документация, которая могла бы помочь мне с этим?Я нашел функцию для этого на веб-сайте Apache, но она не показывает точно, как работает функция;просто существует функция (BinaryHeap (логическое isMinHeap)).

Answer 1

Я думаю, что это будет работать!

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 2

Если добавить подробное решение с поддержкой java generics, его будет относительно легче отслеживать.

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;
}

Answer 3

Статья Википедии должна помочь вам.

Вот несколько вопросов, которые помогут вам задуматься о решении:

1. Что должно быть правдой в отношении корнякучи, предполагая, что куча является минимальной кучей?
2. Если корень кучи удовлетворяет свойству минимальной кучи, как вы гарантируете, что поддеревья корня также содержат свойство?