Package algs24

Class XFixedMinPQ<K extends Comparable<? super K>>

java.lang.Object

algs24.XFixedMinPQ<K>

All Implemented Interfaces:

Iterable<K>

public class XFixedMinPQ<K extends Comparable<? super K>>
extends Object
implements Iterable<K>

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	XFixedMinPQ.HeapIterator

Field Summary

Fields

Modifier and Type	Field	Description
private final int	MAXN
private int	N
private final K[]	pq

Constructor Summary

Constructors

Constructor	Description
XFixedMinPQ(int initCapacity)	Create an empty priority queue with the given initial capacity, using the given comparator.

Method Summary

Modifier and Type	Method	Description
K	delMin()	Delete and return the smallest key on the priority queue.
private void	exch(int i, int j)
private boolean	greater(int i, int j)
void	insert(K x)	Add a new key to the priority queue.
boolean	isEmpty()	Is the priority queue empty?
boolean	isFull()	Is the priority queue full?
private boolean	isMinHeap()
private boolean	isMinHeap(int k)
Iterator<K>	iterator()	Return an iterator that iterates over all of the keys on the priority queue in ascending order.
static void	main(String[] args)	A test client.
K	min()	Return the smallest key on the priority queue.
private void	showHeap()
private void	sink(int k)
int	size()	Return the number of items on the priority queue.
private void	swim(int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

pq

private final K extends Comparable<? super K>[] pq

N

private int N

MAXN

private final int MAXN

Constructor Details

XFixedMinPQ

public XFixedMinPQ(int initCapacity)

Create an empty priority queue with the given initial capacity, using the given comparator.

Method Details

isEmpty

public boolean isEmpty()

Is the priority queue empty?

isFull

public boolean isFull()

Is the priority queue full?

size

public int size()

Return the number of items on the priority queue.

min

public K min()

Return the smallest key on the priority queue. Throw an exception if the priority queue is empty.

insert

public void insert(K x)

Add a new key to the priority queue.

delMin

public K delMin()

Delete and return the smallest key on the priority queue. Throw an exception if the priority queue is empty.

swim

private void swim(int k)

sink

private void sink(int k)

greater

private boolean greater(int i,
 int j)

exch

private void exch(int i,
 int j)

isMinHeap

private boolean isMinHeap()

isMinHeap

private boolean isMinHeap(int k)

iterator

public Iterator<K> iterator()

Return an iterator that iterates over all of the keys on the priority queue in ascending order.

The iterator doesn't implement remove() since it's optional.

Specified by:

iterator in interface Iterable<K extends Comparable<? super K>>

showHeap

private void showHeap()

main

public static void main(String[] args)

A test client.