List backed Generic Heap Data Structure with Heap Sort Algorithm in Java

Introduction

The foremost reason for me blogging on Heap data structure and Heap Sort algorithm emanates from my difficulty in finding a generic, complete, simple and easy to understand implementation in Java on web.

Hope this post would be insightful for the budding Java programmers in the similar fashion as the Heap data structure and Heap Sort algorithm is for solving many simpler to complex problems in day to day life of a programmer.

Heap Definition

A Heap is a data structure modeled over a Binary Tree that satisfies Heap Property. In a Heap each element is assigned a key value or weight.
When an element with lower value key always have a parent node with higher-value key among all nodes, the structure is termed as max-heap and therefore the top of the pile (the root node) has the highest value key.
When an element with higher value key always have the lower value key as parent node among all nodes, the structure is termed as min-heap and therefore the top of the pile (the root node) has the lowest value key.

Not indulging any more into the standard definitions (they can easily be found in abundance on web), we will move quickly to implement Heap data structure (Max-Heap) and Heap Sort algorithm in Java. If you like to explore the theoretical part further in-depth the following links should suffice.
Wiki: Heap Data Structure
Wiki: Heapsort

The implementation touches upon the following Heap concepts:

• Building Generic List backed Heap Data structure (Operation: Heapify)
• Inserting new element into Heap (Operation: siftUp)
• Deleting from Heap (Operation: siftDown)
• Sorting the Heap (Operation: sort)

Java Implementation 

The source code provided here can be accessed on my Github "Gists" with syntax highlight and better formatting and readability.
Here goes the links to Github.
Heap.java
HeapTestHarness.java

Just copy the above file into your Eclipse Java project and run the HeapTestHarness.java as Java Application to play around with implementation and various scenarios.

Sample Output from Test Harness

List backed data structure to demonstrate Heap and Heap Sort Algorithm: [5, 3, 2, 9, 11]
Sorted Heap: [2, 3, 5, 9, 11]
Insertion of new element(12) in the heap: [12, 3, 2, 9, 11, 5]
Deletion from the heap(top node): [5, 3, 2, 9, 11]
Heap Sort Again: [2, 3, 5, 9, 11]

Do post your comments and suggestions and share it if it's useful.
If you would like to have more such articles, kindly leave your request in the comment section.