在优先级队列(堆)中查找最小值 [英] Finding the Minimum in a Priority Queue (heap)

问题描述

我正在尝试学习如何使用优先级队列，有一种我不完全了解的方法，希望对它的工作方式有所帮助.该方法是findMin.

I am trying to learn the how to use Priority Queues, and there is one method I do not fully understand and would like some help as to how it works. That method is findMin.

我想理解的部分是为什么最大的数字最终出现在数组的位置0?

然后，由于列表已排序，因此很容易在数组的位置[1]中找到最小的数字.但是为什么呢?

Then, since the list is sorted, its easy to find the smallest number in location [1] of the array. But why?

这是我正在查看的所有代码:

Here is all the code I am looking at:

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...)

推荐答案

二进制最小堆使用heapify()函数将最小值传播到顶部.插入，删除和更改键操作可以更改最小值，因此调用heapify方法将更改后的节点移动到堆中的正确位置

A binary min heap propogates the minimum to the top using a heapify() function. Insertion, deletion, and change key operations can change the minimum value, so the heapify method is called to move the changed nodes to their correct positions in the heap

这篇关于在优先级队列(堆)中查找最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！