用于检查具有n个元素的数组是否为最小堆的算法 [英] Algorithm for checking if an Array with n-elements is a minimum heap
本文介绍了用于检查具有n个元素的数组是否为最小堆的算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试概述一种算法,以确定我的数组是否为最小堆。是否有任何文档可以帮助我解决这个问题?我在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屋!
查看全文