u6
Class ArrayHeap

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

public class ArrayHeap

extends Heap

Array based implementation of Heap Data Structure. The nodes of binary tree of the heap are stored in a lenear structure.

Fields inherited from class u6.Heap

cmp, height, size

Constructor Summary

ArrayHeap(java.util.Comparator cmp)
Constructs an empty heap with the specified comparator

ArrayHeap(java.util.Comparator comparator, Item[] items)
Bottom-Up construction.

Method Summary

void	add(Item entry) Adds the given item in the heap and updates the size and the height values.
void	bottomUp(int sInx) Constructs the items of the subarray starting from loInx, i.e. items[sInx..size - 1] into the heap container.
protected void	downBubbling() Restores the order-property of the heap, in the case it's violated by the root.
protected void	downBubbling(int index) Locally restores the order-property at the node with the given (absolute) index and the given last node.
Item	extractItem() Extracts the root of the Heap and updates the size and the height values.
java.lang.Object	readMinElement() Reads the element value of the item, stored in the root of the heap without removing the root.
java.lang.Object	readMinKey() Reads the key, stored in the root of the heap, without extracting the root.
protected void	swap(int i, int j) Swaps the elements with index i and j.
java.lang.Object[]	toArray(java.lang.Object[] a)
protected void	upBubbling() Restores the order-property of the heap, in the case it's violated by the last node.
protected void	upBubbling(int index) Locally restores the order-property at the node with the given (absolute) index.

Methods inherited from class u6.Heap

add, computeHeight, getHeight, isEmpty, size

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayHeap

public ArrayHeap(java.util.Comparator cmp)

Constructs an empty heap with the specified comparator

ArrayHeap

public ArrayHeap(java.util.Comparator comparator,
                 Item[] items)

Bottom-Up construction. Constructs a heap and fills it with the objects from items using an algorithm for bottom-up construction.

Method Detail

bottomUp

public void bottomUp(int sInx)

Constructs the items of the subarray starting from loInx, i.e. items[sInx..size - 1] into the heap container.

add

public void add(Item entry)

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

Overrides:

add in class Heap

extractItem

public Item extractItem()

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

Overrides:

extractItem in class Heap

readMinKey

public java.lang.Object readMinKey()

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

Overrides:

readMinKey in class Heap

readMinElement

public java.lang.Object readMinElement()

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

Overrides:

readMinElement in class Heap

upBubbling

protected void upBubbling()

Restores the order-property of the heap, in the case it's violated by the last node.

downBubbling

protected void downBubbling()

Restores the order-property of the heap, in the case it's violated by the root.

upBubbling

protected void upBubbling(int index)

Locally restores the order-property at the node with the given (absolute) index.

downBubbling

protected void downBubbling(int index)

Locally restores the order-property at the node with the given (absolute) index and the given last node.

swap

protected void swap(int i,
                    int j)

Swaps the elements with index i and j.

toArray

public java.lang.Object[] toArray(java.lang.Object[] a)