在優先級隊列（堆）中尋找最小值

Question

我想了解如何使用優先級隊列，並且有一種方法我不完全理解，並且希望得到一些有關它如何工作的幫助。該方法是findMin。

我想了解的部分是爲什麼最大數字最終位於數組的位置0？

然後，由於列表已排序，所以很容易在數組的位置[1]中找到最小的數字。但爲什麼？

這裏是所有我在看的代碼：

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> 
{ 
/** 
* Construct the binary heap. 
*/ 
public BinaryHeap() 
{ 
    this(DEFAULT_CAPACITY); 
} 

/** 
* Construct the binary heap. 
* @param capacity the capacity of the binary heap. 
*/ 
public BinaryHeap(int capacity) 
{ 
    currentSize = 0; 
    array = (AnyType[]) new Comparable[ capacity + 1 ]; 
} 

/** 
* Construct the binary heap given an array of items. 
*/ 
public BinaryHeap(AnyType [ ] items) 
{ 
     currentSize = items.length; 
     array = (AnyType[]) new Comparable[ (currentSize + 2) * 11/10 ]; 

     int i = 1; 
     for(AnyType item : items) 
      array[ i++ ] = item; 
     buildHeap(); 
} 

/** 
* Insert into the priority queue, maintaining heap order. 
* Duplicates are allowed. 
* @param x the item to insert. 
*/ 
public void insert(AnyType x) 
{ 
    if(currentSize == array.length - 1) 
     enlargeArray(array.length * 2 + 1); 

     // Percolate up 
    int hole = ++currentSize; 
    for(array[ 0 ] = x; x.compareTo(array[ hole/2 ]) < 0; hole /= 2) 
     array[ hole ] = array[ hole/2 ]; 
    array[ hole ] = x; 
} 


private void enlargeArray(int newSize) 
{ 
     AnyType [] old = array; 
     array = (AnyType []) new Comparable[ newSize ]; 
     for(int i = 0; i < old.length; i++) 
      array[ i ] = old[ i ];   
} 

/** 
* Find the smallest item in the priority queue. 
* @return the smallest item, or throw an UnderflowException if empty. 
*/ 
public AnyType findMin() 
{ 
    if(isEmpty()) 
     return null; 
    return array[ 1 ]; 
} 

/** 
* Remove the smallest item from the priority queue. 
* @return the smallest item, or throw an UnderflowException if empty. 
*/ 
public AnyType deleteMin() 
{ 
    if(isEmpty()) 
     return null; 

    AnyType minItem = findMin(); 
    array[ 1 ] = array[ currentSize-- ]; 
    percolateDown(1); 

    return minItem; 
} 

/** 
* Establish heap order property from an arbitrary 
* arrangement of items. Runs in linear time. 
*/ 
private void buildHeap() 
{ 
    for(int i = currentSize/2; i > 0; i--) 
     percolateDown(i); 
} 

/** 
* Test if the priority queue is logically empty. 
* @return true if empty, false otherwise. 
*/ 
public boolean isEmpty() 
{ 
    return currentSize == 0; 
} 

/** 
* Make the priority queue logically empty. 
*/ 
public void makeEmpty() 
{ 
    currentSize = 0; 
} 

public String toString(int i){ 
    return array[ i ].toString(); 
} 

private static final int DEFAULT_CAPACITY = 10; 

private int currentSize;  // Number of elements in heap 
private AnyType [ ] array; // The heap array 

/** 
* Internal method to percolate down in the heap. 
* @param hole the index at which the percolate begins. 
*/ 
private void percolateDown(int hole) 
{ 
    int child; 
    AnyType tmp = array[ hole ]; 

    for(; hole * 2 <= currentSize; hole = child) 
    { 
     child = hole * 2; 
     if(child != currentSize && 
       array[ child + 1 ].compareTo(array[ child ]) < 0) 
      child++; 
     if(array[ child ].compareTo(tmp) < 0) 
      array[ hole ] = array[ child ]; 
     else 
      break; 
    } 
    array[ hole ] = tmp; 
} 

    // Test program 
public static void main(String [ ] args) 
{ 

    BinaryHeap<Integer> h = new BinaryHeap<>(); 
    for (int i = 0; i < 100 ; i++){ 
     h.insert(i); 
    } 
    System.out.println("The Size of the array is " + h.currentSize); 
    System.out.println("The smaller number on the array is " + h.findMin()); 

    System.out.println(); 

    for (int i = 0; i < 100 ; i++){ 
     System.out.println("Object in location " + i + " is " + h.toString(i)); 
    } 

} 
} 

此輸出：

The Size of the array is 100 
The smaller number on the array is 0 

Object in location 0 is 99 
Object in location 1 is 0 
Object in location 2 is 1 (add 1 to each side and so on...) 

Answer 1

二進制分鐘堆propogates最低至使用heapify（）函數的頂部。插入，刪除和更改鍵操作可以更改最小值，因此調用heapify方法將更改的節點移動到堆中的正確位置。

Answer 2

因爲在for循環中有array [0] = x。