Heap sort uses a binary heap, which is a complete binary tree. A binary tree is a hierarchical structure. It either is empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree. The length of a path is the number of the edges in the path. The depth of a node is the length of the path from the root to the node.
A heap is a binary tree with the following properties:
- It is a complete binary tree.
- Each node is greater than or equal to any of its children.
Complete Binary Tree
A binary tree is complete if each of its levels is full, except that the last level may not be full and all the leaves on the last level are placed leftmost. For example, in below Figure, the binary trees in (a) and (b) are complete, but the binary trees in (c) and (d) are not complete. Further, the binary tree in (a) is a heap, but the binary tree in (b) is not a heap, because the root (39) is less than its right child (42).
 |
| Binary Tree Illustration |
To sort an array using a heap, first create an object using the Heap class, add all the elements to the heap using the add method, and remove all the elements from the heap using the remove method. The elements are removed in descending order. Below code Listing gives an algorithm for sorting an array using a heap.
Heap.java
public class Heap<E extends Comparable>
{
private ArrayList<E> list = new ArrayList<E>();
/** Create a
default heap */
public Heap() {
}
/** Create a heap
from an array of objects */
public Heap(E[] objects) {
for (int i = 0; i <
objects.length; i++)
add(objects[i]);
}
/** Add a new
object into the heap */
public void add(E newObject) {
list.add(newObject); // Append to the
heap
int currentIndex = list.size() - 1; // The index of the
last node
while (currentIndex >
0) {
int parentIndex =
(currentIndex - 1) / 2;
// Swap if the
current object is greater than its parent
if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {
E
temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex,
temp);
}
else
break; // The tree is a
heap now
currentIndex
= parentIndex;
}
}
/** Remove the root
from the heap */
public E remove() {
if (list.size() == 0)
return null;
E
removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 *
currentIndex + 1;
int rightChildIndex = 2
* currentIndex + 2;
// Find the maximum
between two children
if (leftChildIndex
>= list.size())
break; // The tree is a
heap
int maxIndex =
leftChildIndex;
if (rightChildIndex
< list.size()) {
if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
maxIndex
= rightChildIndex;
}
}
// Swap if the
current node is less than the maximum
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
E
temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex,
temp);
currentIndex
= maxIndex;
}
else
break; // The tree is a
heap
}
return removedObject;
}
/** Get the number
of nodes in the tree */
public int getSize() {
return list.size();
}
}
HeapSort.java
public class HeapSort {
/** Heap sort
method */
public static <E extends Comparable>
void heapSort(E[] list) {
// Create a Heap of
integers
Heap<E>
heap = new Heap<E>();
// Add elements to
the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);
// Remove elements
from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i]
= heap.remove();
}
/** A test method */
public static void main(String[] args)
{
Integer[]
list = { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
heapSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
When you run this Code listing it will produce output like:
-2 1 2 2 3 3 5 6 12 14
Reference(s): Introduction to JAVA by Y. Daniel Liang
No comments:
Post a Comment