package edu.columbia.cs.cs1007.datastructures;
import java.util.ArrayList;
/**
* An implementation of the min-heap.
*
* @author Julia Stoyanovich (jds2109@columbia.edu)
* COMS 1007, Summer 2009
*
*/
public class MinHeap {
private ArrayList<Node> _heap;
private int _heapSize;
private class Node {
public int _key;
public int _val;
public Node(int key, int val) {
_key = key;
_val = val;
}
public int getKey() {
return _key;
}
public int getVal() {
return _val;
}
public void setVal(int val) {
_val = val;
}
public String toString() {
return "" + _val;
}
public Node getParent() {
if (_key == 0) {
return null;
}
int parentKey = (_key+1)/2 - 1;
return _heap.get(parentKey);
}
public Node getLeft() {
int parentKey = 2*(_key + 1) - 1;
if (parentKey >= _heap.size()) {
return null;
}
return _heap.get(parentKey);
}
public Node getRight() {
int parentKey = 2*(_key + 1);
if (parentKey >= _heap.size()) {
return null;
}
return _heap.get(parentKey);
}
}
/**
* Initialize a heap with values from an array.
* @param values
*/
public MinHeap(int[] values) {
_heap = new ArrayList<Node>();
for (int i=0; i<values.length; i++) {
_heap.add(new Node(i, values[i]));
}
_heapSize = _heap.size();
}
/**
* Test whether the current heap fulfills the
* heap property: parents are no higher than children.
* @return
*/
public boolean isHeap() {
boolean res = true;
for (int i=1; i<_heap.size(); i++) {
Node currNode = _heap.get(i);
if (currNode._val < currNode.getParent().getVal()) {
res = false;
break;
}
}
return res;
}
/**
* Heapify at position i.
* @param i
*/
public void heapify(int i) {
Node currNode = _heap.get(i);
Node leftNode = currNode.getLeft();
Node rightNode = currNode.getRight();
Node smallest = currNode;
if ((leftNode != null) &&
(leftNode.getKey() < _heapSize) &&
(leftNode.getVal() < currNode.getVal())) {
smallest = leftNode;
}
if ((rightNode != null) &&
(rightNode.getKey() < _heapSize) &&
(rightNode.getVal() < smallest.getVal())) {
smallest = rightNode;
}
if (smallest != currNode) {
int tmpVal = currNode.getVal();
currNode.setVal(smallest.getVal());
smallest.setVal(tmpVal);
heapify(smallest.getKey());
}
}
/**
* If parent of the node idenfified by key
* has a higher value, swap the two values,
* and return the key of the parent.
* @param key
* @return key of the parent if there was a swap,
* 0 if we reached the root, -1 if there was no swap.
*/
public int swapWithParent(int key) {
Node node = _heap.get(key);
Node parent = node.getParent();
if (parent == null) {
return 0; // reached the root
}
if (node.getVal() < parent.getVal()) {
int tmpVal = node.getVal();
node.setVal(parent.getVal());
parent.setVal(tmpVal);
return parent.getKey();
}
return -1; // found the right position
}
/**
* Insert a new element into the heap.
* @param val - value to be inserted
*/
public void insert(int val) {
Node newNode = new Node(_heap.size(), val);
_heap.add(newNode);
int key = newNode.getKey();
do {
key = swapWithParent(key);
} while (key > 0);
}
/**
* Build heap from an initial state bottom-up,
* by repeatedly calling heapify, starting from the
* right-most node in the 2nd to last level.
*/
public void buildHeap() {
for (int i=(_heap.size() - 1)/2; i>=0; i--) {
heapify(i);
}
_heapSize = _heap.size();
}
/**
* Perform heapSort in a heap, by repeatedly
* removing the minimum element, placing the
* last element into the position of the root,
* and calling heapify on the root.
*
* Finally, we transform the heap into an array
* that sorts elements in ascending order, and
* return that array.
*
* @return array, sorted in ascending order
*/
public int[] heapSort() {
buildHeap();
for (int i=_heap.size()-1; i>0; i--) {
Node firstNode = _heap.get(0);
Node ithNode = _heap.get(i);
int tmpVal = firstNode.getVal();
firstNode.setVal(ithNode.getVal());
ithNode.setVal(tmpVal);
_heapSize--;
heapify(0);
}
int[] sorted = new int[_heap.size()];
for (int i=0; i<sorted.length; i++) {
sorted[i] = _heap.get(sorted.length-i-1).getVal();
}
return sorted;
}
/**
* Generate a string representation of the heap.
* @return string representation
*/
public String toString() {
StringBuffer res = new StringBuffer();
for (int i=0; i<_heap.size(); i++) {
Node node = _heap.get(i);
res.append(i + " [Node " + node.toString());
if (node.getParent() != null) {
res.append(" Parent " + node.getParent().getVal());
}
if (node.getLeft() != null) {
res.append(" Left " + node.getLeft().getVal());
}
if (node.getRight() != null) {
res.append(" Right " + node.getRight().getVal());
}
res.append("]\n");
}
return res.toString();
}
/**
* Generate a string representation of an array.
* @param inArr
* @return string representation
*/
public static String arrayToString(int[] inArr) {
StringBuffer res = new StringBuffer();
for (int num : inArr) {
res.append(" " + num);
}
return res.toString();
}
public static void main(String[] args) {
int[] values = {1, 4, 5, 3, 10, 3, 28, 6, 11, 11};
MinHeap heap = new MinHeap(values);
System.out.println("Initial state. A heap? " + heap.isHeap());
System.out.println(heap.toString());
heap.buildHeap();
System.out.println("After a call to heapify. A heap? " + heap.isHeap());
System.out.println(heap.toString());
heap.insert(4);
System.out.println("After inserting 4. A heap? " + heap.isHeap());
System.out.println(heap.toString());
heap.insert(0);
System.out.println("After inserting 0. A heap? " + heap.isHeap());
System.out.println(heap.toString());
heap.insert(44);
System.out.println("After inserting 44. A heap? " + heap.isHeap());
System.out.println(heap.toString());
System.out.println("Sorted array:");
int[] sorted = heap.heapSort();
System.out.println(arrayToString(sorted));
}
}
|