算法檢查是否有n元素的數組是最小堆

Question

我想概述一個算法來確定我的數組是否是最小堆。有沒有任何文件可以幫助我呢？我在Apache的網站上找到了它的一個函數，但它沒有精確地顯示函數的工作方式;只是存在一個函數（BinaryHeap（boolean isMinHeap））。

Answer 1

The Wikipedia article應該可以幫到你。

這裏有一些問題讓你思考的解決方案：

1. 什麼必須是真實的關於堆的根，假設堆是最小堆？
2. 如果堆的根滿足min heap屬性，那麼如何確保根的子樹也包含該屬性？
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; 
}