Приоритетные очереди реализация бинарной кучи в

Приоритетные очереди абстрактных типов данных (ADT) поддерживает следующие три операции:

  • add an element to the queue with an associated priority
  • remove the element from the queue that has the highest priority, and return it
  • (optionally) peek at the element with highest priority without removing it

Простейший способ реализации приоритетного очередь типом данных является сохранение ассоциативный массив отображения каждой из приоритетных в список элементов с этого приоритета. Если ассоциация списков или хэш-таблиц, используемых для осуществления ассоциативный массив, добавив элемент имеет постоянную времени, но удаление или заглядывать на элементом первостепенной важности занимает линейного (O (N)) время, потому что мы должны искать все ключи для крупнейших . Если самобалансирующейся бинарных деревьев поиска используются все три операции принимают O (журнал N) раз, это популярное решение в среде, которая уже обеспечивает сбалансированные деревья, но ничего более сложного. Ван Эмде Боаса деревом, другой ассоциативный массив структур данных, может выполнять все три операции в O (Вход Вход п), но в пространстве стоимость для малых очередях около O (2 ^ (M / 2)), где М число бит в приоритетном значении, которое может быть непомерно высокой.

Есть целый ряд специализированных куча структур данных, либо предоставить дополнительные операции или превосходят описанных выше подходов. Бинарной кучи использует O (журнал N) время для обеих операций, но позволяет заглядывать на элементом первостепенной важности, не снимая ее в фиксированное время. Биномиальные кучами добавить еще несколько операций, но они требуют вывода (журнал N) времени заглядывать. Фибоначчи кучах можно вставить элементы, взглянуть на максимальный элемент приоритета, и снижение приоритетности элементов в амортизированной постоянная времени (удаление еще O (журнал N)).

Следующий код показывает, как реализовать приоритетные очереди в Java:


// BinaryHeap class

//

// CONSTRUCTION: empty or with initial array.

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x )       --> Insert x

// Comparable deleteMin( )--> Return and remove smallest item

// Comparable findMin( )  --> Return smallest item

// boolean isEmpty( )     --> Return true if empty; else false

// void makeEmpty( )      --> Remove all items

// ******************ERRORS********************************

// Throws UnderflowException for findMin and deleteMin when empty



/**

 * Implements a binary heap.

 * Note that all "matching" is based on the compareTo method.

 @author Mark Allen Weiss

 */

public class BinaryHeap implements PriorityQueue {

    /**

     * Construct the binary heap.

     */

    public BinaryHeap( ) {

        currentSize = 0;

        array = new ComparableDEFAULT_CAPACITY + ];

    }

    

    /**

     * Construct the binary heap from an array.

     @param items the inital items in the binary heap.

     */

    public BinaryHeapComparable [ ] items ) {

        currentSize = items.length;

        array = new Comparableitems.length + ];

        

        forint i = 0; i < items.length; i++ )

            arrayi + = items];

        buildHeap( );

    }

    

    /**

     * Insert into the priority queue.

     * Duplicates are allowed.

     @param x the item to insert.

     @return null, signifying that decreaseKey cannot be used.

     */

    public PriorityQueue.Position insertComparable x ) {

        ifcurrentSize + == array.length )

            doubleArray( );

        

        // Percolate up

        int hole = ++currentSize;

        array= x;

        

        for; x.compareToarrayhole / ] ) 0; hole /= )

            arrayhole = arrayhole / ];

        arrayhole = x;

        

        return null;

    }

    

    /**

     @throws UnsupportedOperationException because no Positions are returned

     * by the insert method for BinaryHeap.

     */

    public void decreaseKeyPriorityQueue.Position p, Comparable newVal ) {

        throw new UnsupportedOperationException"Cannot use decreaseKey for binary heap" );

    }

    

    /**

     * Find the smallest item in the priority queue.

     @return the smallest item.

     @throws UnderflowException if empty.

     */

    public Comparable findMin( ) {

        ifisEmpty( ) )

            throw new UnderflowException"Empty binary heap" );

        return array];

    }

    

    /**

     * Remove the smallest item from the priority queue.

     @return the smallest item.

     @throws UnderflowException if empty.

     */

    public Comparable deleteMin( ) {

        Comparable minItem = findMin( );

        array= arraycurrentSize-- ];

        percolateDown);

        

        return minItem;

    }

    

    /**

     * Establish heap order property from an arbitrary

     * arrangement of items. Runs in linear time.

     */

    private void buildHeap( ) {

        forint i = currentSize / 2; i > 0; i-- )

            percolateDown);

    }

    

    /**

     * Test if the priority queue is logically empty.

     @return true if empty, false otherwise.

     */

    public boolean isEmpty( ) {

        return currentSize == 0;

    }

    

    /**

     * Returns size.

     @return current size.

     */

    public int size( ) {

        return currentSize;

    }

    

    /**

     * Make the priority queue logically empty.

     */

    public void makeEmpty( ) {

        currentSize = 0;

    }

    

    private static final int DEFAULT_CAPACITY = 100;

    

    private int currentSize;      // Number of elements in heap

    private Comparable [ ] array; // The heap array

    

    /**

     * Internal method to percolate down in the heap.

     @param hole the index at which the percolate begins.

     */

    private void percolateDownint hole ) {

        int child;

        Comparable tmp = arrayhole ];

        

        for; hole * <= currentSize; hole = child ) {

            child = hole * 2;

            ifchild != currentSize &&

                    arraychild + ].compareToarraychild ] ) )

                child++;

            ifarraychild ].compareTotmp )

                arrayhole = arraychild ];

            else

                break;

        }

        arrayhole = tmp;

    }

    

    /**

     * Internal method to extend array.

     */

    private void doubleArray( ) {

        Comparable [ ] newArray;

        

        newArray = new Comparablearray.length * ];

        forint i = 0; i < array.length; i++ )

            newArray= array];

        array = newArray;

    }

    

    // Test program

    public static void mainString [ ] args ) {

        int numItems = 10000;

        BinaryHeap h1 = new BinaryHeap( );

        Integer [ ] items = new IntegernumItems - ];

        

        int i = 37;

        int j;

        

        fori = 37, j = 0; i != 0; i = i + 37 % numItems, j++ ) {

            h1.insertnew Integer) );

            itemsnew Integer);

        }

        

        fori = 1; i < numItems; i++ )

            if( ((Integer)( h1.deleteMin( ) )).intValue( ) != i )

                System.out.println"Oops! " + i );

        

        BinaryHeap h2 = new BinaryHeapitems );

        fori = 1; i < numItems; i++ )

            if( ((Integer)( h2.deleteMin( ) )).intValue( ) != i )

                System.out.println"Oops! " + i );

    }

}



// PriorityQueue interface

//

// ******************PUBLIC OPERATIONS*********************

// Position insert( x )   --> Insert x

// Comparable deleteMin( )--> Return and remove smallest item

// Comparable findMin( )  --> Return smallest item

// boolean isEmpty( )     --> Return true if empty; else false

// void makeEmpty( )      --> Remove all items

// int size( )            --> Return size

// void decreaseKey( p, v)--> Decrease value in p to v

// ******************ERRORS********************************

// Throws UnderflowException for findMin and deleteMin when empty



/**

 * PriorityQueue interface.

 * Some priority queues may support a decreaseKey operation,

 * but this is considered an advanced operation. If so,

 * a Position is returned by insert.

 * Note that all "matching" is based on the compareTo method.

 @author Mark Allen Weiss

 */

public interface PriorityQueue {

    /**

     * The Position interface represents a type that can

     * be used for the decreaseKey operation.

     */

    public interface Position {

        /**

         * Returns the value stored at this position.

         @return the value stored at this position.

         */

        Comparable getValue( );

    }

    

    /**

     * Insert into the priority queue, maintaining heap order.

     * Duplicates are allowed.

     @param x the item to insert.

     @return may return a Position useful for decreaseKey.

     */

    Position insertComparable x );

    

    /**

     * Find the smallest item in the priority queue.

     @return the smallest item.

     @throws UnderflowException if empty.

     */

    Comparable findMin( );

    

    /**

     * Remove the smallest item from the priority queue.

     @return the smallest item.

     @throws UnderflowException if empty.

     */

    Comparable deleteMin( );

    

    /**

     * Test if the priority queue is logically empty.

     @return true if empty, false otherwise.

     */

    boolean isEmpty( );

    

    /**

     * Make the priority queue logically empty.

     */

    void makeEmpty( );

    

    /**

     * Returns the size.

     @return current size.

     */

    int size( );

    

    /**

     * Change the value of the item stored in the pairing heap.

     * This is considered an advanced operation and might not

     * be supported by all priority queues. A priority queue

     * will signal its intention to not support decreaseKey by

     * having insert return null consistently.

     @param p any non-null Position returned by insert.

     @param newVal the new value, which must be smaller

     *    than the currently stored value.

     @throws IllegalArgumentException if p invalid.

     @throws UnsupportedOperationException if appropriate.

     */

    void decreaseKeyPosition p, Comparable newVal );

}





/**

 * Exception class for access in empty containers

 * such as stacks, queues, and priority queues.

 @author Mark Allen Weiss

 */

public class UnderflowException extends RuntimeException {

    /**

     * Construct this exception object.

     @param message the error message.

     */

    public UnderflowExceptionString message ) {

        supermessage );

    }

}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>