Heap vs priority_queue?

Heap algorithms (make_heap, push_heap, pop_heap) operate on raw containers; priority_queue is a container adapter wrapping heap operations with cleaner API.

make_heap: O(n), push_heap: O(log n), pop_heap: O(log n), sort_heap: O(n log n).

When use heap over set?

Heap for priority queue (top element access, O(1) top, O(log n) push/pop); set for ordered traversal (O(log n) all operations).

[2026] C++ Heap Algorithms: make_heap, push_heap, pop_heap, sort_heap, and priority_queue

Q: Max heap vs min heap?

Default is max heap (std::less). For min heap, use std::greater or custom comparator.

2026년 3월 12일 · 20분 읽기 · 수정 2026년 3월 12일 Intermediate Tutorial

이 글의 핵심

Master C++ heap algorithms: make_heap, push_heap, pop_heap, sort_heap, priority_queue, and production patterns.

Why Heap Algorithms Matter

Problem: Priority Queue Operations

Problem: You need:

Fast access to max/min element (O(1))
Efficient insertion (O(log n))
Efficient removal (O(log n)) Solution: Heap data structure (binary heap). 다음은 mermaid를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

flowchart TD
    subgraph Max Heap
        A[100]
        B[80]
        C[90]
        D[50]
        E[70]
        F[60]
        G[85]
        A --> B
        A --> C
        B --> D
        B --> E
        C --> F
        C --> G
    end

Heap property: Parent ≥ children (max heap) or parent ≤ children (min heap).

Heap Fundamentals
make_heap: Build Heap
push_heap: Insert Element
pop_heap: Remove Max
sort_heap: Heap Sort
priority_queue: Container Adapter
Custom Comparators
Production Patterns
Complete Example

1. Heap Fundamentals

Binary Heap Structure

Binary heap: Complete binary tree stored in array. 아래 코드는 code를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

Array: [100, 80, 90, 50, 70, 60, 85]
Index:   0   1   2   3   4   5   6
Tree:
       100
      /   \
    80     90
   / \    / \
  50 70  60 85

Parent-child relationship:

Parent of i: (i - 1) / 2
Left child of i: 2 * i + 1
Right child of i: 2 * i + 2

Max Heap vs Min Heap

Type	Property	Root
Max heap	Parent ≥ children	Maximum element
Min heap	Parent ≤ children	Minimum element

2. make_heap: Build Heap

Syntax

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

template<class RandomIt>
void make_heap(RandomIt first, RandomIt last);
template<class RandomIt, class Compare>
void make_heap(RandomIt first, RandomIt last, Compare comp);

Example: Max Heap

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    std::make_heap(vec.begin(), vec.end());
    
    std::cout << "Max heap: ";
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    
    std::cout << "Max element: " << vec.front() << "\n";
}

Output:

Max heap: 9 6 4 3 5 1 2 1
Max element: 9

Complexity: O(n)

Example: Min Heap

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(vec.begin(), vec.end(), std::greater<int>());
std::cout << "Min heap: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::cout << "Min element: " << vec.front() << "\n";

Output:

Min heap: 1 1 2 3 5 9 4 6
Min element: 1

3. push_heap: Insert Element

Syntax

template<class RandomIt>
void push_heap(RandomIt first, RandomIt last);

Usage

Precondition: [first, last-1) is already a heap. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::vector<int> vec = {9, 6, 4, 3, 5, 1, 2, 1};
// vec is already a max heap
vec.push_back(8);  // Add to end
std::push_heap(vec.begin(), vec.end());  // Restore heap property
std::cout << "After push: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::cout << "Max element: " << vec.front() << "\n";

Output:

After push: 9 8 4 6 5 1 2 1 3
Max element: 9

Complexity: O(log n)

How push_heap Works

아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

flowchart TD
    A[1. Add element to end]
    B[2. Compare with parent]
    C{Parent < child?}
    D[3. Swap with parent]
    E[4. Move up]
    F[Done]
    A --> B
    B --> C
    C -->|Yes| D
    D --> E
    E --> B
    C -->|No| F

4. pop_heap: Remove Max

Syntax

template<class RandomIt>
void pop_heap(RandomIt first, RandomIt last);

Usage

Postcondition: Max element moved to last-1, [first, last-1) is heap. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::vector<int> vec = {9, 8, 4, 6, 5, 1, 2, 1, 3};
// vec is a max heap
std::pop_heap(vec.begin(), vec.end());  // Move max to end
int max = vec.back();
vec.pop_back();  // Remove max
std::cout << "Popped: " << max << "\n";
std::cout << "After pop: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";

Output:

Popped: 9
After pop: 8 6 4 3 5 1 2 1

Complexity: O(log n)

How pop_heap Works

다음은 mermaid를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

flowchart TD
    A[1. Swap root with last]
    B[2. Move last to end]
    C[3. Compare with children]
    D{Smaller than max child?}
    E[4. Swap with max child]
    F[5. Move down]
    G[Done]
    A --> B
    B --> C
    C --> D
    D -->|Yes| E
    E --> F
    F --> C
    D -->|No| G

5. sort_heap: Heap Sort

Syntax

template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last);

Usage

Precondition: [first, last) is a heap. Postcondition: [first, last) is sorted (ascending for max heap). 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(vec.begin(), vec.end());
std::cout << "Heap: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::sort_heap(vec.begin(), vec.end());
std::cout << "Sorted: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";

Output:

Heap: 9 6 4 3 5 1 2 1
Sorted: 1 1 2 3 4 5 6 9

Complexity: O(n log n) Note: After `sort_heap`, the range is no longer a heap.

6. priority_queue: Container Adapter

What is priority_queue?

priority_queue: Container adapter that wraps heap operations. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Basic Usage

#include <queue>
#include <iostream>
int main() {
    std::priority_queue<int> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    
    std::cout << "Priority queue (max heap):\n";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << "\n";
}

Output:

Priority queue (max heap):
5 4 3 1 1

Min Priority Queue

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
min_pq.push(1);
min_pq.push(5);
std::cout << "Min priority queue:\n";
while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";
    min_pq.pop();
}
std::cout << "\n";

Output:

Min priority queue:
1 1 3 4 5

7. Custom Comparators

Custom Struct

다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

struct Task {
    std::string name;
    int priority;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // Max heap by priority
    }
};
int main() {
    std::priority_queue<Task> pq;
    
    pq.push({"Task A", 3});
    pq.push({"Task B", 1});
    pq.push({"Task C", 5});
    pq.push({"Task D", 2});
    
    std::cout << "Tasks by priority:\n";
    while (!pq.empty()) {
        const auto& task = pq.top();
        std::cout << task.name << " (priority: " << task.priority << ")\n";
        pq.pop();
    }
}

Output: 아래 코드는 code를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

Tasks by priority:
Task C (priority: 5)
Task A (priority: 3)
Task D (priority: 2)
Task B (priority: 1)

Lambda Comparator

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority;  // Max heap
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);
pq.push({"Task A", 3});
pq.push({"Task B", 1});
pq.push({"Task C", 5});
while (!pq.empty()) {
    std::cout << pq.top().name << "\n";
    pq.pop();
}

Output:

Task C
Task A
Task B

8. Production Patterns

Pattern 1: Top K Elements

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

std::vector<int> top_k(const std::vector<int>& data, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    
    for (int x : data) {
        if (min_heap.size() < k) {
            min_heap.push(x);
        } else if (x > min_heap.top()) {
            min_heap.pop();
            min_heap.push(x);
        }
    }
    
    std::vector<int> result;
    while (!min_heap.empty()) {
        result.push_back(min_heap.top());
        min_heap.pop();
    }
    
    std::reverse(result.begin(), result.end());
    return result;
}
int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    auto top3 = top_k(data, 3);
    
    std::cout << "Top 3: ";
    for (int x : top3) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

Output:

Top 3: 9 6 5

Complexity: O(n log k)

Pattern 2: Merge K Sorted Arrays

다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

struct Element {
    int value;
    int array_index;
    int element_index;
    
    bool operator>(const Element& other) const {
        return value > other.value;  // Min heap
    }
};
std::vector<int> merge_k_sorted(const std::vector<std::vector<int>>& arrays) {
    std::priority_queue<Element, std::vector<Element>, std::greater<Element>> min_heap;
    
    // Initialize heap with first element from each array
    for (int i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            min_heap.push({arrays[i][0], i, 0});
        }
    }
    
    std::vector<int> result;
    
    while (!min_heap.empty()) {
        auto elem = min_heap.top();
        min_heap.pop();
        
        result.push_back(elem.value);
        
        // Add next element from same array
        int next_index = elem.element_index + 1;
        if (next_index < arrays[elem.array_index].size()) {
            min_heap.push({
                arrays[elem.array_index][next_index],
                elem.array_index,
                next_index
            });
        }
    }
    
    return result;
}
int main() {
    std::vector<std::vector<int>> arrays = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    
    auto merged = merge_k_sorted(arrays);
    
    std::cout << "Merged: ";
    for (int x : merged) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

Output:

Merged: 1 2 3 4 5 6 7 8 9

Complexity: O(n log k), where n = total elements, k = number of arrays.

Pattern 3: Task Scheduler

struct Task {
    std::string name;
    int priority;
    std::chrono::system_clock::time_point deadline;
    
    bool operator<(const Task& other) const {
        if (priority != other.priority) {
            return priority < other.priority;  // Higher priority first
        }
        return deadline > other.deadline;  // Earlier deadline first
    }
};
class TaskScheduler {
public:
    void add_task(const Task& task) {
        tasks_.push(task);
    }
    
    std::optional<Task> get_next_task() {
        if (tasks_.empty()) {
            return std::nullopt;
        }
        
        Task task = tasks_.top();
        tasks_.pop();
        return task;
    }
    
    std::size_t pending_count() const {
        return tasks_.size();
    }
private:
    std::priority_queue<Task> tasks_;
};
int main() {
    TaskScheduler scheduler;
    
    auto now = std::chrono::system_clock::now();
    
    scheduler.add_task({"Task A", 3, now + std::chrono::hours(2)});
    scheduler.add_task({"Task B", 5, now + std::chrono::hours(1)});
    scheduler.add_task({"Task C", 3, now + std::chrono::hours(1)});
    scheduler.add_task({"Task D", 1, now + std::chrono::hours(3)});
    
    std::cout << "Task execution order:\n";
    while (auto task = scheduler.get_next_task()) {
        std::cout << task->name << " (priority: " << task->priority << ")\n";
    }
}

Output: 아래 코드는 code를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

Task execution order:
Task B (priority: 5)
Task C (priority: 3)
Task A (priority: 3)
Task D (priority: 1)

Key: Priority queue for task scheduling with priority and deadline.

9. Complete Example

#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <chrono>
#include <random>
// Benchmark heap operations
void benchmark_heap() {
    std::vector<int> data(100000);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(1, 1000000);
    
    for (auto& x : data) {
        x = dis(gen);
    }
    
    // make_heap
    auto start = std::chrono::high_resolution_clock::now();
    std::make_heap(data.begin(), data.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto make_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    // push_heap
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        data.push_back(dis(gen));
        std::push_heap(data.begin(), data.end());
    }
    end = std::chrono::high_resolution_clock::now();
    auto push_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    // pop_heap
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        std::pop_heap(data.begin(), data.end());
        data.pop_back();
    }
    end = std::chrono::high_resolution_clock::now();
    auto pop_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    std::cout << "Heap Benchmark (100K elements):\n";
    std::cout << "make_heap: " << make_time << " μs\n";
    std::cout << "push_heap (1K ops): " << push_time << " μs\n";
    std::cout << "pop_heap (1K ops): " << pop_time << " μs\n";
}
int main() {
    // Demo: Basic heap operations
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    std::cout << "Original: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\n\n";
    
    std::make_heap(vec.begin(), vec.end());
    std::cout << "After make_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nMax: " << vec.front() << "\n\n";
    
    vec.push_back(10);
    std::push_heap(vec.begin(), vec.end());
    std::cout << "After push_heap(10): ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nMax: " << vec.front() << "\n\n";
    
    std::pop_heap(vec.begin(), vec.end());
    int max = vec.back();
    vec.pop_back();
    std::cout << "After pop_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nPopped: " << max << "\n\n";
    
    std::sort_heap(vec.begin(), vec.end());
    std::cout << "After sort_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\n\n";
    
    // Benchmark
    benchmark_heap();
}

Output: 다음은 code를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

Original: 3 1 4 1 5 9 2 6
After make_heap: 9 6 4 3 5 1 2 1
Max: 9
After push_heap(10): 10 9 4 6 5 1 2 1 3
Max: 10
After pop_heap: 9 6 4 3 5 1 2 1
Popped: 10
After sort_heap: 1 1 2 3 4 5 6 9
Heap Benchmark (100K elements):
make_heap: 1234 μs
push_heap (1K ops): 567 μs
pop_heap (1K ops): 543 μs

Summary

Key Operations

Operation	Complexity	Purpose
make_heap	O(n)	Build heap from range
push_heap	O(log n)	Insert element
pop_heap	O(log n)	Remove max/min
sort_heap	O(n log n)	Sort heap (destroys heap)
is_heap	O(n)	Check if range is heap
Heap algorithms provide efficient priority queue operations with O(log n) insertion and removal.

Keywords

C++ heap, make_heap, push_heap, pop_heap, sort_heap, priority_queue, binary heap One-line summary: Master C++ heap algorithms (make_heap, push_heap, pop_heap, sort_heap) and priority_queue for efficient priority queue operations, task scheduling, and top-K problems.

이 글의 핵심

Why Heap Algorithms Matter

Problem: Priority Queue Operations

Heap property: Parent ≥ children (max heap) or parent ≤ children (min heap).

Table of Contents

1. Heap Fundamentals

Binary Heap Structure

Max Heap vs Min Heap

2. make_heap: Build Heap

Syntax

Example: Max Heap

Example: Min Heap

3. push_heap: Insert Element

Syntax

Usage

How push_heap Works

4. pop_heap: Remove Max

Syntax

Usage

How pop_heap Works

5. sort_heap: Heap Sort

Syntax

Usage

Complexity: O(n log n) Note: After sort_heap, the range is no longer a heap.

6. priority_queue: Container Adapter

What is priority_queue?

Basic Usage

Min Priority Queue

7. Custom Comparators

Custom Struct

Lambda Comparator

8. Production Patterns

Pattern 1: Top K Elements

Pattern 2: Merge K Sorted Arrays

Pattern 3: Task Scheduler

Key: Priority queue for task scheduling with priority and deadline.

9. Complete Example

Summary

Key Operations

Keywords

Complexity: O(n log n) Note: After `sort_heap`, the range is no longer a heap.