> ## Content Index
> Fetch the complete content index at: https://sleepyforest.magicbytes.top/llms.txt
> Use this file to discover other available public pages before exploring further.

# Data Structure (6) - Heaps & Priority Queues
- URL: https://sleepyforest.magicbytes.top/data-structure-part6-heaps-and-priority-queues/
- Published: 2021-10-04T13:57:00.000Z
- Updated: 2021-10-06T17:45:25.000Z
- Author: Betty
- Tags: C++, 数据结构, #Import 2026-08-29 09:17

## ADT

- insert(value)
- remove()
- isEmpty()

Where value is among int, string, double, char... or objects that supports < operator.

# Heap

Unsorted Array: O(1)\* insert, O(n) removeMin (need to find min first)

Unsorted Linked List: O(1) insert, O(n) removeMin

Sorted Array: O(n)\* insert, O(1) removeMin

Sorted Linked List: O(n) insert, O(1) removeMin

It's easier to removeMin on sorted structures and insert on unsorted structures.

To balance the worst case time to O(lg(n)) insert and O(lg(n)) removeMin, we could use a binary tree.

## Definition

### (min-)Heap

A complete binary tree t is a min-heap if:

- T = {} or
- T = {r, TL, TR} where r is less than roots of {TL , TR} and {TL , TR} are min-heaps.

Logically it's a tree, and implementation-wise, it's an array.

![](https://strapi.fluere.cloud/uploads/example_a_min_heap_454ad16d0e.png)

Example: a min-heap

The heap above in array would be: \[1, 4, 5, 12, 7, 6, 8, 13, 14, null, null, 11, null, null, null\]

We could define left must be larger or smaller than right, but as long as all roots are smaller than their children, it's a min-heap.

Priority queues are based on heaps.

## Operations

- Left child of node\[i\]: node\[2\*i\]
- Right child of node\[i\]: node\[2\*i + 1\]
- Parent of node\[i\]: floor(i/2)

We could also store the number of nodes, n, in node\[0\], and the above remains the same. Knowing the number of nodes can help you know where in the array is outside of the heap.

### How to Insert

```cpp
template <class T>
void Heap<T>::_insert(const T & key) {
    // check if there's enough space
    if (size_ == capacity) {
        _growArray();
    }
    
    // insert element at the end of array
    item_[++size] = key;
    
    // restore heap property
    _heapifyUp();
}

template <class T>
void Heap<T>::_heapifyUp(size_t index) {
    if(index>1) { // 1 is the root here, as we stored size in 0
        if(item_[index] < item_[parent(index)]) {
            std::swap(item_[index], item_[parent(index));
            _heapifyUp(parent(index));
        }
    }
}
```

### How to Remove

removeMin() is removing root of a min-heap, and removeMax() is removing root of a max-heap.

When removing root:

1. Swap root with the last node.
2. Remove the last node (root).
3. Heapify to restore heap property

```cpp
template <class T>
T Heap<T>::_remove() {
    T min_value = item_[1];
    item_[1] = item_[size--]; // swap with last and delete
    
    _heapifyDown();
    return min_value; // return original root value
}

template <class T>
void Heap<T>::_heapifyDown(size_t index=1) {
    if(!_isLeaf(index)) {
        size_t minChildIndex = _minChild(index);
        if(item_[index] > item_[minChildIndex]) {
            std::swap(item_[index], item_[minChildIndex]);
            _heapifyDown(minChildIndex);
        }
    }
}
```

### How to Build a Heap

buildHeap - heapifyUp: O(n\*log(n)) – each insert is O(log(n))

```cpp
void Heap<T>::buildHeap() {
    for(unsigned i=2; i<= size_; i++) {
        heapifyUp(i);
        // takes O(n logn)
    }
}
```

buildHeap - heapifyDown: O(n) – takes time of O(sum of the height of all sub trees)

```
void Heap<T>::buildHeap() {
    for(unsigned i=parent(size_); i>0; i--) {
        heapifyDown(i);
        // takes O(n)
    }
}
```

Prove heap building running time:

- S(h): Sum of heights of all nodes in a complete tree of h
- S(0) = 0
- S(1) = 1 + 0 + 0 = 1
- S(2) = 2 + 1 + 1 = 4
- ....
- S(h) = h + 2 \* S(h-1) = 2(h+1) \-h - 2
- Since h<=lg(n),
- O(2(lg(n)+1) \- lg(n) -2) = O(n-2-lg(n)) = O(n)