u6
Class Heap

java.lang.Object
  |
  +--u6.Heap

Direct Known Subclasses:

ArrayHeap

public abstract class Heap

extends java.lang.Object

Abstract Heap class. A heap is a binary tree that stores a collection of keys at its internal nodes and that satisfies two additional properties:
1. Heap-Order Property: for every node v other than the root the key stored at v is greater than or equal to the key stored at v's parent.
2. Complete Binary Tree: the levels 0, 1, ... (height - 1) have the maximum number of nodes possible and in level (height - 1) all the nodes are to the left.

Field Summary

protected java.util.Comparator	cmp Comparator, defining a total relation on the keys
protected int	height The height of the heap; a heap with one element has height = 1.
protected int	size The number of elements in this heap

Constructor Summary

Heap(java.util.Comparator cmp)
Constructs an empty heap with the given comparator.

Method Summary

abstract void	add(Item entry) Adds the given item in the heap and updates the size and the height values.
void	add(java.lang.Object key, java.lang.Object value) Adds a node with the given key and value in the heap and updates the size and the height values.
static int	computeHeight(int size) Computes the height of a heap with a given size.
abstract Item	extractItem() Extracts the root of the Heap and updates the size and the height values.
int	getHeight() Reads the height of the heap.
boolean	isEmpty() Checks whether the heap is empty.
abstract java.lang.Object	readMinElement() Reads the element value of the item, stored in the root of the heap without removing the root.
abstract java.lang.Object	readMinKey() Reads the key, stored in the root of the heap, without extracting the root.
int	size() Reads the number of items stored in the heap.

Methods inherited from class java.lang.Object

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

Field Detail

size

protected int size

The number of elements in this heap

height

protected int height

The height of the heap; a heap with one element has height = 1.

cmp

protected java.util.Comparator cmp

Comparator, defining a total relation on the keys

Constructor Detail

Heap

public Heap(java.util.Comparator cmp)

Constructs an empty heap with the given comparator.

Method Detail

add

public void add(java.lang.Object key,
                java.lang.Object value)

Adds a node with the given key and value in the heap and updates the size and the height values.

add

public abstract void add(Item entry)

Adds the given item in the heap and updates the size and the height values.

extractItem

public abstract Item extractItem()

Extracts the root of the Heap and updates the size and the height values.

readMinKey

public abstract java.lang.Object readMinKey()

Reads the key, stored in the root of the heap, without extracting the root.

readMinElement

public abstract java.lang.Object readMinElement()

Reads the element value of the item, stored in the root of the heap without removing the root.

size

public int size()

Reads the number of items stored in the heap.

getHeight

public int getHeight()

Reads the height of the heap.

isEmpty

public boolean isEmpty()

Checks whether the heap is empty.

computeHeight

public static int computeHeight(int size)

Computes the height of a heap with a given size.