Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Diagnostics
    Standard Library – Part 1
    Function Objects
    Standard Library – Part 2
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    Standard Library Heap OperationsHeap OperationsHeap Ops

    Background Background

    What Are Heaps? General

    • family of data structures (not to be confused with the memory partition for dynamic storage)
    • store objects (keys) that can be ordered
    • referred to as "max-heap" or "min-heap" depending on the ordering
    • are usually used to implement priority queues
    • get maximum usually in O(1) (constant time)
    • remove maximum usually in O(log N) (logarithmic time)
    • insert new key usually in O(1) or O(log N)
    • increase/decrease key change value of a key, usually in O(1) or O(log N)

    The Heap Data Structure

    Binary Max Heaps Binary Max

    • keys are stored in nodes of a binary tree
    • keys must be orderable, i.e., comparable
    • heap property: all children of a parent with key P must contain keys than are smaller or equal to P ⇒ root has maximum
    • get maximum: O(1) (constant time)
    • remove maximum: O(log N) (logarithmic time)
    • insert: O(log N)
    • increase key: O(log N)

    Representing Binary Trees With Arrays Representing Binary Trees Array Rep.

    • The tree must either consist of a single node or it must be complete on all inner levels, i.e., every inner node must have exactly 2 children.
    • The rightmost leafs might be missing.


    Heap Manipulation Manipulate

    Heaps In The C++ Standard Library C++ Standard Library Heaps Std.Lib.Heaps


    • make_heap: reorder a sequence of keys into a binary heap
    • push_heap: insert a new key
    • pop_heap: remove maximum

    If all you want is a priority queue, use the dedicated standard container type std::priority_queue .

    Initialize Heap Init

    std::vector<int> h {1,6,4,2,9,7,8};
    // make max heap (default)
    make_heap(begin(h), end(h));
    for(int x : h) { cout << x << ' '; }  // 9 6 8 2 1 7 4
    // make min heap
    make_heap(begin(h), end(h), std::greater<>{});
    for(int x : h) { cout << x << ' '; }  // 1 2 4 9 6 7 8
    std::vector<int> h {1,6,4,2,9,7,8};
    // make max heap (default)
    std::ranges::make_heap(h});
    for(int x : h) { cout << x << ' '; }  // 9 6 8 2 1 7 4
    // make min heap
    std::ranges::make_heap(h, std::{greater<>{});
    for(int x : h) { cout << x << ' '; }  // 1 2 4 9 6 7 8

    Shrink Heap Shrink

    // max heap:
    std::vector<int> h {9,6,8,2,1,4,7};
    // remove element from heap:
    pop_heap(begin(h), end(h));
    auto oldmax = h.back();  // oldmax = 9
    h.pop_back();
    for(int x : h) { cout << x << ' '; }  // 8 6 7 2 1 4
    // max heap:
    std::vector<int> h {9,6,8,2,1,4,7};
    // remove element from heap:
    std::ranges::pop_heap(h);
    auto oldmax = h.back();  // oldmax = 9
    h.pop_back();
    for(int x : h) { cout << x << ' '; }  // 8 6 7 2 1 4

    Example: Successive Shrinking Example

    Grow Heap Grow

    // max heap:
    std::vector<int> h {8,6,7,2,1,4};
    // add new element to heap:
    h.push_back(9);
    push_heap(begin(h), end(h));
    for(int x : h) { cout << x << ' '; }  // 9 6 8 2 1 4 7
    // max heap:
    std::vector<int> h {8,6,7,2,1,4};
    // add new element to heap:
    h.push_back(9);
    std::ranges::push_heap(h);
    for(int x : h) { cout << x << ' '; }  // 9 6 8 2 1 4 7

    Example: Successive Growing Example

    Auxiliary Operations Auxiliary Ops Auxiliary Ops

    sort_heap (Heap → Sorted Array) sort_heap

    // max heap:
    std::vector<int> h {9,6,8,2,1,7,4};
    // make sorted vector:
    sort_heap(begin(h), end(h));
    for(int x : h) { cout << x << ' '; }  // 1 2 4 6 7 8 9
    // max heap:
    std::vector<int> h {9,6,8,2,1,7,4};
    // make sorted vector:
    std::ranges::sort_heap(h);
    for(int x : h) { cout << x << ' '; }  // 1 2 4 6 7 8 9

    is_heap is_heap

    // max heap:
    std::vector<int> h {9,7,8,6,2,1,4};
    cout << is_heap(begin(h), end(h));  // true
    // not a max heap:
    std::vector<int> v {1,2,3,4,5};
    cout << is_heap(begin(v), end(v));  // false
    // max heap:
    std::vector<int> h {9,7,8,6,2,1,4};
    cout << std::ranges::is_heap(h);  // true
    // not a max heap:
    std::vector<int> v {1,2,3,4,5};
    cout << std::ranges::is_heap(v);  // false

    is_heap_until is_heap_until

    std::vector<int> h {9,7,8,6,8,1,4};
    auto e = is_heap_until(begin(h), end(h));
    if(e == end(h)) {
      cout << "complete heap!"; 
    } else {
      cout << *e;  // 8
      auto const idx = distance(begin(h), e);  // 4
      cout << "heap until index " << idx;
      // add one more element to heap
      push_heap(begin(h), next(e));
      
    }
    std::vector<int> h {9,7,8,6,8,1,4};
    auto e = std::ranges::is_heap_until(h);
    if(e == end(h)) {
      cout << "complete heap!"; 
    } else {
      cout << *e;  // 8
      auto const idx = distance(begin(h), e);  // 4
      cout << "heap until index " << idx;
      // erase non-heap part
      h.erase(e, end(h));
      
    }