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 Operations Heap Operations Heap Ops

    Background Background

    What Are Heaps? General

    • a family of data structures (not to be confused with the memory partition for dynamic storage)
    • they contain objects (keys) that can be ordered
    • they are referred to as "max-heap" or "min-heap" depending on the ordering
    • they 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
    Binary max heaps
    • 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.
    • The rightmost leafs might be missing.

    Example of how to represent a binary tree with an array.

    Example of how to represent a binary tree with an array.

    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

    std::vector<int> h {1,2,4,9,8,7,6};
    make_heap(begin(h), end(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
    
    std::vector<int> h {1,2,4,9,8,7,6};
    std::ranges::make_heap(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

    pop_heap example

    Grow Heap Grow

    std::vector<int> h {1,2,4,8,6,7};
    make_heap(begin(h), end(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
    
    std::vector<int> h {1,2,4,8,6,7};
    std::ranges::make_heap(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

    push_heap 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 C++11

    // 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 C++11

    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!\n"; 
    } 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!\n"; 
    } 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));
      
    }