我想概述一個算法來確定我的數組是否是最小堆。有沒有任何文件可以幫助我呢?我在Apache的網站上找到了它的一個函數,但它沒有精確地顯示函數的工作方式;只是存在一個函數(BinaryHeap(boolean isMinHeap))。算法檢查是否有n元素的數組是最小堆
2
A
回答
1
The Wikipedia article應該可以幫到你。
這裏有一些問題讓你思考的解決方案:
- 什麼必須是真實的關於堆的根,假設堆是最小堆?
- 如果堆的根滿足min heap屬性,那麼如何確保根的子樹也包含該屬性?
- 如果樹的根沒有孩子會怎麼樣?這是一個小堆嗎?
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;
}
1
添加一個詳細的解決方案與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;
}
相關問題
- 1. 檢查樹是否是最小堆
- 2. 檢查數組是否有空元素
- 3. 如何檢查數組是否是最小堆?
- 4. 檢查數組元素是否存在
- 5. 檢查數組是否爲空元素
- 6. 檢查數組元素是否爲鍵
- 7. 檢查數組元素是否爲空
- 8. 檢查數組中的所有元素是否相等的最快方法
- 9. jquery檢查元素是否有元素
- 10. 檢查numpy數組中的所有元素是否匹配
- 11. 檢查數組是否有1個以上的元素
- 12. jQuery - 檢查元素是否有數組中的類?
- 13. javascript-檢查數組中的元素是否是特定變量
- 14. php:檢查字符串是否以數組元素結尾的最佳方法?
- 15. 檢查數組中是否有任何重複元素遞歸
- 16. 檢查數組是否有兩個元素
- 17. 算法檢查泛型類型的數組是否是MaxHeap
- 18. 如何檢查數組中的所有元素是否都是正整數?
- 19. 檢查元素是否有兩個類
- 20. 檢查DOM元素是否有焦點
- 21. 檢查元素是否有孩子?
- 22. 從最小或最大堆中刪除根元素的算法
- 23. 在大小爲N的數組的每k個元素中查找最小元素和第二小元素
- 24. Typescript檢查M大小數組中是否有「任何n個連續元素相同」
- 25. 如何檢查double是否至多有n位小數?
- 26. 檢查元素是否是列表中的最後一個
- 27. 在排序中查找數組中第n個最小元素?
- 28. 如何檢查堆棧的前兩個元素是否存在?
- 29. 最小堆算法
- 30. 檢查數字是否有小數點