Heap Sort in Java

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();
              }
       }

 

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

Newer Post Older Post

Leave a Reply

naeemgik. Powered by Blogger.