用于检查具有n个元素的数组是否为最小堆的算法 [英] Algorithm for checking if an Array with n-elements is a minimum heap

问题描述

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

I'm trying to outline an algorithm to determine if my array is a minimum heap. Is there any documentation out there that could help me with this? I found a function for it on Apache's website, but it doesn't show exactly how the function works; just that there exists a function (BinaryHeap(boolean isMinHeap)).

推荐答案

添加带有Java泛型支持的详细解决方案，相对而言比较容易。

Adding a verbose solution with java generics support, it is relatively easier to follow.

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

这篇关于用于检查具有n个元素的数组是否为最小堆的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！