public class LeftistHeap<E extends java.lang.Comparable<? super E>>
extends java.lang.Object
Definition: The null path length (NPL) of a tree node is the length of the shortest path to a node with 0 children or 1 child. The NPL of a leaf is 0. The NPL of a NULL pointer is -1.
Definition: A leftist tree is a binary tree where at each node the null path length of the left child is greater than or equal to the null path length of the right child.
Definition: A leftist heap is a leftist tree where the value stored at any node is less than or equal to the value stored at either of its children.
Constructor and Description |
---|
LeftistHeap()
Construct the leftist heap.
|
Modifier and Type | Method and Description |
---|---|
E |
deleteMin()
Remove the smallest item from the priority queue.
|
E |
findMin()
Find the smallest item in the priority queue.
|
int |
getSize() |
void |
insert(E x)
Insert into the priority queue, maintaining heap order.
|
boolean |
isEmpty()
Test if the priority queue is logically empty.
|
static void |
main(java.lang.String[] args) |
void |
makeEmpty()
Make the priority queue logically empty.
|
void |
merge(LeftistHeap<E> rhs)
Merge rhs into the priority queue.
|
E[] |
toArray(E[] a,
boolean incr)
Return this heap as an ordered array.
|
public void merge(LeftistHeap<E> rhs)
rhs
- the other leftist heap.public void insert(E x)
x
- the item to insert.public E findMin()
public E deleteMin()
public E[] toArray(E[] a, boolean incr)
incr
- the flag to control order.public boolean isEmpty()
public int getSize()
public void makeEmpty()
public static void main(java.lang.String[] args)