Binary heap
Binary heap use an implicit relationship specified by the indices
1.Introduction
A heap is just a tree with a special property or constraints on the values of its nodes
The tree with special properties or constraints on the value of its nodes these constraint called the heap property the constraint
Heap property
1.Minimum heap
Every node value should be <= value of it's children
The node with the smallest value should be the root of the tree
2.Maximum heap
Every node value should be >= value of it's children
The node with the largest value should be the root of the tree
Shape property
If H is the height of the tree - The leaf nodes should only be at level H or H - 1
Only the last level is incomplete in the heap
All nodes at level H - 1 have to be filled before moving on to level H
The heap should form a complete binary tree - all levels except the last should be filled
2. Logic
The operations typically performed on a heap requires us to
1.Traverse downwards from the root towards.
2.The leaf node Traverse upwards from the leaf nodes towards the root
On the heap we want to be able to
1.Get left child
2.Get right child
3.Get parent
Every level of the binary tree in a heap is filled except perhaps the last
Implement by array:
Node at index i:
has a left child at index: 2i + 1
has a right child at index: 2i + 2
has parent at index: (i - 1)/2
3.Implementation
Base class
A generic heap can hold data of any type
The generic type has to extend comparable - This how we check the highest priority
public abstract class Heap<T extends Comparable> {
private static int MAX_SIZE = 40;
private T[] array;
private int count = 0;
public Heap(Class<T> clazz) {
this(clazz, MAX_SIZE);
}
public Heap(Class<T> clazz, int size) {
array = (T[]) Array.newInstance(clazz, size);
}
public int getLeftChild(int index) {
int leftChildIndex = 2 * index + 1;
if (leftChildIndex >= count) {
return -1;
}
return leftChildIndex;
}
public int getRightChild(int index) {
int rightChildIndex = 2 * index + 2;
if (rightChildIndex >= count) {
return -1;
}
return rightChildIndex;
}
public int getParentIndex(int index) {
if (ijndex < 0 || index > count) {
return -1;
}
return (index - 1)/2;
}
protected void swap(int index1, int index2) {
T tempValue = array[index1];
array[index1] = array[index2];
array[index1] = tempValue;
}
}4.Heapify
While inserting or removing an element into the heap how do we know which is the right position for the element to occupy?
Sift down
An element is in the wrong position with respect to other elements bellow it in the heap
It has to be moved downwards in the heap towards the leaf nodes to find it's right position
protected void siftDown(int index) {
int leftIndex = getLeftChildIndex(index);
int rightIndex = getRightChildIndex(index);
int smallerIndex = -1;
if (leftIndex != -1 && rightIndex != -1) {
smallerIndex = getElementAtIndex(leftIndex).compareTo(getElementAtIndex(rightIndex)) < 0
? leftIndex : rightIndex;
} else if (leftIndex != -1) {
smallerIndex = leftIndex;
} else if (rightIndex != -1) {
smallerIndex = rightIndex;
}
if (smallerIndex == -1) {
return;
}
if (getElementAtIndex(smallerIndex).compareTo(getElementAtIndex(index)) < 0) {
swap(smallerIndex, index);
siftDown(smallerIndex);
}
}Sift up
An element is in the wrong position with respect to other elements above it in the heap
It has to be moved upwards in the heap towards the leaf nodes to find it's right position
public void siftUp(int index){
int parentIndex = getParentIndex(index);
if (parentIndex != -1 &&
getElementAtIndex(index).compareTo(getElementAtIndex(parentIndex)) < 0) {
swap(parentIndex, index);
siftUp(parentIndex);
}
}5.Insert
插在Array的最後面, 然後Sift up上來
public void insert(T value) throws HeapFullExcepton {
if (count >= array.length) {
throw HeapFullExcepton);
}
account[count] = value;
siftUp(count);
count++;
}6.Remove
移除最小值 (array[0])
將最大值移到root
Sift down root
public T removeHighestPriority()(T value) throws HeapEmptyExcepton {
T min = getighestPriority();
array[0] = array[count - 1];
if (count >= array.length) {
throw HeapFullExcepton);
}
account[count] = value;
count--;
siftDown(0);
return min;
}
public T getighestPriority() throws HeapEmptyExcepton {
if (count == 0) {
throw HeapEmptyExcepton);
}
return array[0];
}7.Complexity
Insert: O(log n)
Access: O(1)
Remove: O(log n)
8.Find the maximum element in a minimum heap
先找出最後一個node
比較所有leaf node的大小 (最大值一定是其中一個leaf)
public static int getMaximum(MinHeap<Integer> minHeap) {
int lastIndex = minHeap.getCount() - 1;
int lastParentIndex = minHeap.getParentIndex();
int firstChildIndex = lastParentIndex + 1;
int maxElement = minHeap.getParentIndex(firstChildIndex);
for (int i = firstChildIndex; i <= lastIndex; i++) {
if (maxElement < minHeap.getElementAtIndex(i)) {
maxElement = minHeap.getElementAtIndex(i);
}
}
return maxElement;
}9.Find the K largest elements in a stream
Use a minimum heap with size K to store elements as they come in
public static void printMaximumElements(int k) throws MinHeap.HeapEmptyExcepton,
MinHeap.HeapFullExcepton{
MinHeap<Integer> minHeap = new MinHeap<>(Integer.class, k);
for (int number : randomNumber) {
if (minHeap.isEmpty()) {
minHeap.insert(number);
} else if (!minHeap.isFull || minHeap.getHighestPriority() < number) {
if (minHeap.isFull()) {
minHeap.removeHighestPriority();
}
minHeap.insert(number);
}
}
minHeap.printArray();
}
10.Merge K sorted arrays using heaps
Remove the smallest element from each list and add it to the minimum heap - there will be K elements in the heap
public static void mergeKSortedLists(int totalElements, List<Integer... lists>)
throws MinHeap.HeapEmptyExcepton, MinHeap.HeapFullExcepton{
MinHeap<Element> minHeap = new MinHeap<>(Element.class, lists.length);
List<Integer> sorted = new ArrayList<>();
for (int i = 0; i < lists.length; i++) {
List<Integer> list = lists[i];
if (!list.isEmpty()) {
minHeap.insert(new Element(i, list.remove(0)));
}
}
while (sortedList.size() < totalElements) {
Element element = minHeap.removeHighestPriority();
sortedList.add(element.getValue());
List<Integer> list = lists[element.getListIndex()];
if (!list.isEmpty()) {
minHeap.insert(new Element(element.getListIndex(), list.remove(0)));
}
}
printList(sortedList);
}11.Find the median elements in a stream
Tips
The stream implies that we have no idea which elements are going in to come in text - we have to keep track of the median as the elements stream in
Use a max heap to store the smaller (first) half of elements seen in the stream
Use a min heap to store the larger (second) half of elements seen in the stream
原則上, min heap及max heap的root都是stream的median elements
min heap的node值都小於平均值, max heap的node值都大於平均值
Implementation
第一個數字放到max heap
接下來的數字依序跟max heap比較, 如果比max heap的root大則放到min heap, 如果比max heap的root小則放到max heap
如果max heap及min heap個數差異超過1, 則必須rebalance: 從min heap中取出最小值並且加入max heap
如果兩個heap的數量相等, 則平均值為兩個heap root的平均值
否則平均值為數量多的heap的root值
public static double getStreamingMedian(int number)
throw MinHeap.HeapEmptyException, MinHeap.HeapFullException{
if (!maxHeap.isEmpty() & number > maxHeap.getHighestPriority()) {
minHeap.insert(number);
} else {
maxHeap.insert(number);
}
//rebalance
if (minHeap.getCount() > maxHeap.getCount() + 1) {
maxHeap.insert(minHeap.removeHighestPriority());
} else if (maxHeap.getCount() > minHeap.getCount() + 1){
minHeap.insert(maxHeap.removeHighestPriority());
}
if (maxHeap.getCount() == minHeap.getCount()) {
return (maxHeap.getHighestPriority() + minHeap.getHighestPriority()) * 0.5;
}
return minHeap.getCount() > maxHeap.getCount()
? minHeap.getHighestPriority()
: maxHeap.getHighestPriority();
}Last updated