Package algs24

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

java.lang.Object

algs24.MyMinMaxPQ<K>

All Implemented Interfaces:

Iterable<K>

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	MyMinMaxPQ.HeapIterator

Field Summary

Fields

Modifier and Type	Field	Description
private K[]	a
private int[]	ab
private K[]	b
private int[]	ba
private int	MAXN
private int	N

Constructor Summary

Constructors

Constructor	Description
MyMinMaxPQ(int capacity)

Method Summary

Modifier and Type	Method	Description
private void	aExch(int ai, int aj)
private boolean	aGreater(int i, int j)
private void	aSink(int k)
private static boolean	assertionsAreOn()
private void	aSwim(int k)
private void	bExch(int bi, int bj)
private boolean	bLess(int i, int j)
private void	bSink(int k)
private void	bSwim(int k)
private void	check()
K	delMax()	Delete and return the largest key on the priority queue.
K	delMin()	Delete and return the smallest key on the priority queue.
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	isMaxHeap(int k)
private boolean	isMinHeap(int k)
private boolean	isMinMaxHeap()
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)
K	min()	Return the smallest key on the priority queue.
private static void	randomEmpty(MyMinMaxPQ<Integer> pq, boolean log)
private static void	randomOps(MyMinMaxPQ<Integer> pq, int NUMOPS, boolean log)
private static MyMinMaxPQ<Integer>	randomPQ(int maxSize)
private static int	randomValue()	A test client.
private void	showHeap()
int	size()	Return the number of items on the priority queue.
private void	swap(int[] a, int i, int j)
private void	swap(K[] a, int i, int j)

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

N

private int N

MAXN

private int MAXN

a

private K extends Comparable<? super K>[] a

b

private K extends Comparable<? super K>[] b

ab

private int[] ab

ba

private int[] ba

Constructor Details

MyMinMaxPQ

public MyMinMaxPQ(int capacity)

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.

delMax

public K delMax()

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

aSwim

private void aSwim(int k)

aSink

private void aSink(int k)

bSwim

private void bSwim(int k)

bSink

private void bSink(int k)

aGreater

private boolean aGreater(int i,
 int j)

bLess

private boolean bLess(int i,
 int j)

swap

private void swap(K[] a,
 int i,
 int j)

swap

private void swap(int[] a,
 int i,
 int j)

aExch

private void aExch(int ai,
 int aj)

bExch

private void bExch(int bi,
 int bj)

showHeap

private void showHeap()

check

private void check()

isMinMaxHeap

private boolean isMinMaxHeap()

isMaxHeap

private boolean isMaxHeap(int k)

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

randomValue

private static int randomValue()

A test client.

randomPQ

private static MyMinMaxPQ<Integer> randomPQ(int maxSize)

randomOps

private static void randomOps(MyMinMaxPQ<Integer> pq,
 int NUMOPS,
 boolean log)

randomEmpty

private static void randomEmpty(MyMinMaxPQ<Integer> pq,
 boolean log)

assertionsAreOn

private static boolean assertionsAreOn()

main

public static void main(String[] args)