Приоритетная очередь не понимает, как отследить алгоритм ⇐ JAVA

[Anonymous]

Вот инструкции, которые я получил...

• Вставьте следующие n объектов в указанном порядке в двоичная минимальная куча, вы должны отслеживать метод push.
  5, 3, 9, 7, 2, 4, 6, 1, 8
• Примените метод pop() 3 раза

Я не понимаю, как извлечь из моего двоичного дерева

вот что у меня есть..

9
/ \
8 6
/\ /\
7 4 5 1
/
3


Это код, который мне нужно отследить и выяснить, как его извлечь.

import java.util.Collection;
import java.util.NoSuchElementException;

/**
* PriorityQueue class implemented via the binary heap.
*/
public class PriorityQueue
{

private static int INITSIZE = 100;

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

/**
* Construct an empty PriorityQueue.
*/
public PriorityQueue( )
{
currentSize = 0;
array = (AnyType[]) new Object[ INITSIZE + 1 ];
}

/**
* Compares lhs and rhs using compareTo
*/
private int compare( AnyType lhs, AnyType rhs ) {
return ((Comparable)lhs).compareTo( rhs );
}

/**
* Inserts an item to this PriorityQueue.
* @param x any object.
* @return true.
*/
public boolean push( AnyType x )
{
if( currentSize + 1 == array.length )
expandArray( );

// Percolate up
int hole = ++currentSize;
array[ 0 ] = x;

for( ; compare( x, array[ hole / 2 ] ) < 0; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;

return true;
}

/**
* isEmpty() indicates whether the heap is empty.
* @return true if the list is empty, false otherwise.
**/

public boolean isEmpty() {
return currentSize == 0;
}

/**
* Returns the number of items in this PriorityQueue.
* @return the number of items in this PriorityQueue.
*/
public int size( )
{
return currentSize;
}

/**
* Make this PriorityQueue empty.
*/
public void clear( )
{
currentSize = 0;
}

/**
* Returns the smallest item in the priority queue.
* @return the smallest item.
* @throws NoSuchElementException if empty.
*/
public AnyType element( )
{
if( isEmpty( ) )
throw new NoSuchElementException( );
return array[ 1 ];
}

/**
* Removes the smallest item in the priority queue.
* @return the smallest item.
* @throws NoSuchElementException if empty.
*/
public AnyType pop( )
{
AnyType minItem = element( );
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 );
}

/**
* 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 i)
min = i;
t.push( new Integer( i ) );
if( ((Integer)(t.element( ))).intValue( ) != min )
System.out.println( "Push error! "+i+" "
+((Integer)(t.element( ))).intValue( ));
}

for( int i = 1; i < NUMS; i++ )
if( ((Integer)(t.pop( ))).intValue( ) != i )
System.out.println( "Pop error!" );
}
}


Подробнее здесь: https://stackoverflow.com/questions/494 ... -alogrithm