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

1. 移除最小值 (array[0])

2. 將最大值移到root

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

1. 第一個數字放到max heap

2. 接下來的數字依序跟max heap比較, 如果比max heap的root大則放到min heap, 如果比max heap的root小則放到max heap

3. 如果max heap及min heap個數差異超過1, 則必須rebalance: 從min heap中取出最小值並且加入max heap

4. 如果兩個heap的數量相等, 則平均值為兩個heap root的平均值

5. 否則平均值為數量多的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();
}