在优先级队列(堆)中查找最小值

本文介绍了在优先级队列(堆)中查找最小值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试学习如何使用优先级队列，有一种我不完全了解的方法，希望对它的工作方式有所帮助.该方法是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; xpareTo( 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 ]pareTo( array[ child ] ) < 0 ) child++; if( array[ child ]pareTo( 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