---
description: Binary heap use an implicit relationship specified by the indices
---

# Binary heap

## 1.Introduction

* A heap is just a tree with a **special property** or constraints on the values of its nodes&#x20;
* The tree with special properties or constraints on the value of its nodes these constraint called the heap property the constraint&#x20;
* 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.&#x20;
  * 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**&#x20;
    * has a **right** child at index: **2i + 2**&#x20;
    * 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 &#x20;

```
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&#x20;

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

