힙의 구조와 push/pop 동작 원리

힙(Heap)은 최소값 또는 최대값을 빠르게 꺼내기 위한 자료구조입니다. 정렬과 비슷해 보이지만 목적이 다릅니다. 힙은 전체 순서를 맞추는 구조가 아니라, 루트 한 칸에 정답 후보를 유지하는 구조입니다.

처음 배우는 단계에서는 힙 배열을 정렬된 배열로 오해하기 쉽습니다. 여기서는 트리 그림보다 배열 인덱스 규칙과 push/pop 복원 과정을 우선 다룹니다. 불변식을 이해하면 우선순위 문제를 안정적으로 풀 수 있습니다.

힙 push/pop 복원 흐름과 배열 인덱스-트리 대응 맵

핵심 개념 정돈: 힙 연산

힙은 트리 그림보다 배열 인덱스 규칙과 불변식을 함께 이해하는 것이 핵심입니다. 코드를 보기 전에 i=3일 때 부모와 자식 인덱스를 직접 계산해 보세요.

힙 불변식은 부모와 자식의 대소 관계를 계속 유지하는 약속입니다. 최소 힙은 모든 노드에서 parent <= child, 최대 힙은 parent >= child를 만족해야 합니다. 최소 힙에서 루트는 항상 현재 전체 최소값이므로 top()으로 바로 꺼낼 수 있습니다.

배열 인덱스 관계는 힙을 구현할 때 트리 링크 대신 쓰는 계산식입니다. 0-based 배열 힙에서 parent=(i-1)//2, left=2i+1, right=2i+2 규칙으로 연결이 결정됩니다. 인덱스 3의 부모는 1, 자식은 7과 8이 되는 이유가 이 식입니다.

복원 연산(sift up/down)은 push/pop 후 깨진 불변식을 되돌리는 절차입니다. 삽입 뒤에는 sift up으로 위로 올리고, 루트 교체 뒤에는 sift down으로 아래로 내립니다. 최소 힙에 1을 넣으면 부모보다 작을 때 swap을 반복해 루트까지 올라가게 됩니다.

힙 연산 설계가 실무에서 중요한 이유

힙은 스케줄링, Top-K, Dijkstra, 이벤트 처리 등 다양한 문제의 핵심 도구입니다.
정렬보다 빠른 것은 아니지만, 최소/최대 값 반복 추출에 특화되어 있습니다.

push/pop 내부 원리를 이해하면 라이브러리 함수 사용 시 디버깅도 쉬워집니다.

push/pop 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

최소 힙에서 push/pop이 어떻게 동작하는지 단계별로 확인합니다.

초기 힙: [2, 4, 7]
연산: push(1) 후 pop()

push(1) 뒤 부모와 비교하며 위로 올려 루트가 1이 됩니다.
pop()은 루트를 제거한 뒤 마지막 원소를 올리고 아래로 내려 재정렬합니다.
결국 루트에는 다시 남은 원소 중 최소값이 위치합니다.

힙 연산: push/pop 상태 추적

문제 의도: 힙 불변식이 push/pop 중 어떻게 유지되는지 시각적으로 확인합니다.
입력 예시: 순서대로 push 5,3,8,1, 이후 반복 pop
출력 예시: 연산 단계별 힙 상태 push는 값을 넣고 힙 규칙을 복구하고, pop은 최솟값(또는 최댓값)을 꺼냅니다.

main.cpp

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void printHeap(priority_queue<int, vector<int>, greater<int>> pq) {
    cout << "[";
    bool first = true;
    while (!pq.empty()) {
        if (!first) cout << ", ";
        cout << pq.top();
        pq.pop();
        first = false;
    }
    cout << "]";
}

void traceHeap(const vector<int>& values) {
    priority_queue<int, vector<int>, greater<int>> h;
    for (int v : values) {
        h.push(v);
        cout << "push " << v << " -> ";
        printHeap(h);
        cout << "\n";
    }
    while (!h.empty()) {
        int x = h.top();
        h.pop();
        cout << "pop  " << x << " -> ";
        printHeap(h);
        cout << "\n";
    }
}

int main() {
    traceHeap({5, 1, 8, 3, 2, 7});
    return 0;
}

Main.java

import java.util.PriorityQueue;

public class Main {
    static void traceHeap(int[] values) {
        PriorityQueue<Integer> h = new PriorityQueue<>();
        for (int v : values) {
            h.offer(v);
            System.out.println("push " + v + " -> " + h);
        }
        while (!h.isEmpty()) {
            int x = h.poll();
            System.out.println("pop  " + x + " -> " + h);
        }
    }

    public static void main(String[] args) {
        traceHeap(new int[]{5, 1, 8, 3, 2, 7});
    }
}

main.py

import heapq

def trace_heap(values):
    h = []
    for v in values:
        heapq.heappush(h, v)
        print("push", v, "->", h)

    while h:
        x = heapq.heappop(h)
        print("pop ", x, "->", h)

trace_heap([5, 1, 8, 3, 2, 7])

main.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn print_heap(h: &BinaryHeap<Reverse<i32>>) {
    let mut copy = h.clone();
    let mut out = Vec::new();
    while let Some(Reverse(v)) = copy.pop() {
        out.push(v);
    }
    println!("{out:?}");
}

fn trace_heap(values: &[i32]) {
    let mut h = BinaryHeap::<Reverse<i32>>::new();
    for &v in values {
        h.push(Reverse(v));
        print!("push {v} -> ");
        print_heap(&h);
    }
    while let Some(Reverse(x)) = h.pop() {
        print!("pop  {x} -> ");
        print_heap(&h);
    }
}

fn main() {
    trace_heap(&[5, 1, 8, 3, 2, 7]);
}

힙 push/pop 재확인 힙 정렬성 검토

삽입 시에는 새 원소가 끝에 붙은 뒤 상향 이동(sift-up)합니다.
삭제 시에는 루트 제거 후 마지막 원소를 루트로 올리고 하향 이동(sift-down)합니다.
이 이동 거리가 트리 높이에 비례하므로 O(log N) 상한이 나옵니다.

평균 시간복잡도: push/pop O(log N)
최악 시간복잡도: push/pop O(log N)
공간복잡도: O(N)

힙 연산: 최소값 조회와 정렬 차이

문제 의도: 힙은 정렬 구조가 아니라 최소값 우선 구조임을 확인합니다.
입력 예시: nums=[9,4,7,1,3,8]
출력 예시: 힙 배열 뷰와 pop 순서 결과 heapify는 전체를 정렬하지 않고, 루트가 최소값이 되도록 배열 모양만 재배치합니다.

main.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {9, 4, 7, 1, 3, 8};
    make_heap(nums.begin(), nums.end(), greater<int>());

    cout << "heap array view: ";
    for (int x : nums) cout << x << " ";
    cout << "\n";

    cout << "min value: " << nums.front() << "\n";

    vector<int> ordered;
    auto cmp = greater<int>();
    while (!nums.empty()) {
        pop_heap(nums.begin(), nums.end(), cmp);
        ordered.push_back(nums.back());
        nums.pop_back();
    }
    cout << "ordered by pop: ";
    for (int x : ordered) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(Arrays.asList(9, 4, 7, 1, 3, 8));
        PriorityQueue<Integer> pq = new PriorityQueue<>(nums);

        System.out.println("heap array view: " + pq); // 내부 표현(정렬 아님)
        System.out.println("min value: " + pq.peek()); // O(1)

        List<Integer> ordered = new ArrayList<>();
        while (!pq.isEmpty()) {
            ordered.add(pq.poll());
        }
        System.out.println("ordered by pop: " + ordered);
    }
}

main.py

import heapq

nums = [9, 4, 7, 1, 3, 8]
heapq.heapify(nums)

print(nums)      # 힙 배열 내부 표현 (정렬 아님)
print(nums[0])   # 최소값 조회 O(1)

ordered = []
while nums:
    ordered.append(heapq.heappop(nums))
print(ordered)   # 전체 pop 시 정렬된 결과

main.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let nums = vec![9, 4, 7, 1, 3, 8];
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for x in nums {
        heap.push(Reverse(x));
    }

    println!("heap array view: {:?}", heap); // 내부 표현(정렬 아님)
    if let Some(min_item) = heap.peek() {
        println!("min value: {}", min_item.0);
    } else {
        println!("min value: none");
    }

    let mut ordered = Vec::new();
    while let Some(Reverse(x)) = heap.pop() {
        ordered.push(x);
    }
    println!("ordered by pop: {:?}", ordered);
}

힙 push/pop 재확인 우선순위 흐름 추적

힙 배열 자체는 전체 정렬 상태가 아닙니다.
루트 최소 보장만 유지하므로 중간 원소 순서는 정렬처럼 보이지 않을 수 있습니다.
이 차이를 이해하지 못하면 힙을 정렬 구조로 오해해 잘못된 코드를 작성하기 쉽습니다.

시간복잡도: 힙 구성+전체 pop 기준 O(N log N)
공간복잡도: O(N)

힙 연산: 최대 힙 시뮬레이션

문제 의도: 언어별 최대 힙 처리 방식(기본 최대힙/부호 반전 등)을 비교합니다.
입력 예시: [3,1,6,4,2,5]
출력 예시: 내림차순 추출 결과 [6,5,4,3,2,1] 최대 힙은 항상 가장 큰 값이 루트로 올라오므로 pop만 반복해도 내림차순이 나옵니다.

main.cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> maxHeapPushPop(const vector<int>& values) {
    priority_queue<int> h;
    for (int v : values) h.push(v);

    vector<int> out;
    while (!h.empty()) {
        out.push_back(h.top());
        h.pop();
    }
    return out;
}

int main() {
    vector<int> ans = maxHeapPushPop({3, 1, 6, 4, 2, 5});
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> maxHeapPushPop(int[] values) {
        PriorityQueue<Integer> h = new PriorityQueue<>();
        for (int v : values) h.offer(-v);

        List<Integer> out = new ArrayList<>();
        while (!h.isEmpty()) out.add(-h.poll());
        return out;
    }

    public static void main(String[] args) {
        System.out.println(maxHeapPushPop(new int[]{3, 1, 6, 4, 2, 5}));
    }
}

main.py

import heapq

def max_heap_pushpop(values):
    h = []
    for v in values:
        heapq.heappush(h, -v)  # 부호 반전

    out = []
    while h:
        out.append(-heapq.heappop(h))
    return out

print(max_heap_pushpop([3, 1, 6, 4, 2, 5]))  # [6, 5, 4, 3, 2, 1]

main.rs

use std::collections::BinaryHeap;

fn max_heap_push_pop(values: &[i32]) -> Vec<i32> {
    let mut h = BinaryHeap::new();
    for &v in values {
        h.push(v);
    }

    let mut out = Vec::new();
    while let Some(x) = h.pop() {
        out.push(x);
    }
    out
}

fn main() {
    println!("{:?}", max_heap_push_pop(&[3, 1, 6, 4, 2, 5]));
}

힙 push/pop 상태 추적 push/pop 재확인

파이썬 기본 힙은 최소 힙이므로 최대 힙이 필요하면 부호 반전 트릭을 사용합니다.
튜플 우선순위나 커스텀 객체를 사용할 때도 같은 원리로 확장 가능합니다.
중요한 기준은 비교 규칙을 명확히 고정하는 것입니다.

시간복잡도: N회 push/pop 기준 O(N log N)
공간복잡도: O(N)

push/pop 시나리오별 힙 운용 비교 관점

힙이 적합한 신호입니다.

최솟값/최댓값을 반복적으로 꺼낸다
전체 정렬은 과한 비용이다
동적으로 값이 추가/삭제된다
우선순위 기반 처리가 필요하다

반대로 임의 인덱스 접근이나 완전 정렬 상태가 핵심이면 힙은 부적합할 수 있습니다.

힙 연산 구현 단순성과 성능 균형점

힙 도입 시 고려할 균형점입니다.

장점: 루트 극값 접근이 빠름
단점: 임의 원소 탐색이 비효율적
장점: 동적 우선순위 처리에 적합
단점: 내부 배열이 정렬되어 있다고 오해하기 쉬움

문제의 목표가 극값 반복 추출인지 우선 확인해야 합니다.

힙 연산: `heapify`와 반복 push 비교(비교 연산 횟수)

문제 의도: 시간 측정 대신 비교 연산 횟수를 세어 두 빌드 방식의 차이를 확인합니다.
입력 예시: values=[9,4,7,1,3,8,2,6,5]
출력 예시: push 비교 횟수, heapify 비교 횟수 이 예제는 속도 대신 비교 횟수를 세므로 환경 차이 없이 두 방식을 비교할 수 있습니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

void siftUp(vector<int>& h, int idx, int& cmpCount) {
    while (idx > 0) {
        int p = (idx - 1) / 2;
        cmpCount++;
        if (h[p] <= h[idx]) break;
        swap(h[p], h[idx]);
        idx = p;
    }
}

void siftDown(vector<int>& h, int idx, int& cmpCount) {
    int n = static_cast<int>(h.size());
    while (true) {
        int left = idx * 2 + 1;
        if (left >= n) break;
        int right = left + 1;
        int child = left;
        if (right < n) {
            cmpCount++;
            if (h[right] < h[left]) child = right;
        }
        cmpCount++;
        if (h[idx] <= h[child]) break;
        swap(h[idx], h[child]);
        idx = child;
    }
}

int buildByPush(const vector<int>& values) {
    vector<int> h;
    int cmpCount = 0;
    for (int x : values) {
        h.push_back(x);
        siftUp(h, static_cast<int>(h.size()) - 1, cmpCount);
    }
    return cmpCount;
}

int buildByHeapify(const vector<int>& values) {
    vector<int> h = values;
    int cmpCount = 0;
    for (int i = static_cast<int>(h.size()) / 2 - 1; i >= 0; --i) {
        siftDown(h, i, cmpCount);
    }
    return cmpCount;
}

int main() {
    vector<int> values = {9, 4, 7, 1, 3, 8, 2, 6, 5};
    cout << "push comparisons: " << buildByPush(values) << "\n";
    cout << "heapify comparisons: " << buildByHeapify(values) << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static void siftUp(List<Integer> heap, int idx, int[] cmpCount) {
        while (idx > 0) {
            int p = (idx - 1) / 2;
            cmpCount[0]++;
            if (heap.get(p) <= heap.get(idx)) break;
            int t = heap.get(p);
            heap.set(p, heap.get(idx));
            heap.set(idx, t);
            idx = p;
        }
    }

    static void siftDown(List<Integer> heap, int idx, int[] cmpCount) {
        int n = heap.size();
        while (true) {
            int left = idx * 2 + 1;
            if (left >= n) break;
            int right = left + 1;
            int child = left;
            if (right < n) {
                cmpCount[0]++;
                if (heap.get(right) < heap.get(left)) child = right;
            }
            cmpCount[0]++;
            if (heap.get(idx) <= heap.get(child)) break;
            int t = heap.get(idx);
            heap.set(idx, heap.get(child));
            heap.set(child, t);
            idx = child;
        }
    }

    static int buildByPush(List<Integer> values) {
        List<Integer> heap = new ArrayList<>();
        int[] cmpCount = {0};
        for (int x : values) {
            heap.add(x);
            siftUp(heap, heap.size() - 1, cmpCount);
        }
        return cmpCount[0];
    }

    static int buildByHeapify(List<Integer> values) {
        List<Integer> heap = new ArrayList<>(values);
        int[] cmpCount = {0};
        for (int i = heap.size() / 2 - 1; i >= 0; i--) {
            siftDown(heap, i, cmpCount);
        }
        return cmpCount[0];
    }

    public static void main(String[] args) {
        List<Integer> values = Arrays.asList(9, 4, 7, 1, 3, 8, 2, 6, 5);
        System.out.println("push comparisons: " + buildByPush(values));
        System.out.println("heapify comparisons: " + buildByHeapify(values));
    }
}

main.py

def sift_up(heap, idx, cmp_count):
    while idx > 0:
        p = (idx - 1) // 2
        cmp_count[0] += 1
        if heap[p] <= heap[idx]:
            break
        heap[p], heap[idx] = heap[idx], heap[p]
        idx = p

def sift_down(heap, idx, cmp_count):
    n = len(heap)
    while True:
        left = idx * 2 + 1
        if left >= n:
            break
        right = left + 1
        child = left
        if right < n:
            cmp_count[0] += 1
            if heap[right] < heap[left]:
                child = right
        cmp_count[0] += 1
        if heap[idx] <= heap[child]:
            break
        heap[idx], heap[child] = heap[child], heap[idx]
        idx = child

def build_by_push(values):
    heap = []
    cmp_count = [0]
    for x in values:
        heap.append(x)
        sift_up(heap, len(heap) - 1, cmp_count)
    return cmp_count[0]

def build_by_heapify(values):
    heap = values[:]
    cmp_count = [0]
    for i in range(len(heap) // 2 - 1, -1, -1):
        sift_down(heap, i, cmp_count)
    return cmp_count[0]

values = [9, 4, 7, 1, 3, 8, 2, 6, 5]
print("push comparisons:", build_by_push(values))
print("heapify comparisons:", build_by_heapify(values))

main.rs

fn sift_up(heap: &mut Vec<i32>, mut idx: usize, cmp_count: &mut i32) {
    while idx > 0 {
        let p = (idx - 1) / 2;
        *cmp_count += 1;
        if heap[p] <= heap[idx] {
            break;
        }
        heap.swap(p, idx);
        idx = p;
    }
}

fn sift_down(heap: &mut Vec<i32>, mut idx: usize, cmp_count: &mut i32) {
    let n = heap.len();
    loop {
        let left = idx * 2 + 1;
        if left >= n {
            break;
        }
        let right = left + 1;
        let mut child = left;
        if right < n {
            *cmp_count += 1;
            if heap[right] < heap[left] {
                child = right;
            }
        }
        *cmp_count += 1;
        if heap[idx] <= heap[child] {
            break;
        }
        heap.swap(idx, child);
        idx = child;
    }
}

fn build_by_push(values: &[i32]) -> i32 {
    let mut heap = Vec::new();
    let mut cmp_count = 0;
    for &x in values {
        heap.push(x);
        let last = heap.len() - 1;
        sift_up(&mut heap, last, &mut cmp_count);
    }
    cmp_count
}

fn build_by_heapify(values: &[i32]) -> i32 {
    let mut heap = values.to_vec();
    let mut cmp_count = 0;
    let start = heap.len() / 2;
    for i in (0..start).rev() {
        sift_down(&mut heap, i, &mut cmp_count);
    }
    cmp_count
}

fn main() {
    let values = [9, 4, 7, 1, 3, 8, 2, 6, 5];
    println!("push comparisons: {}", build_by_push(&values));
    println!("heapify comparisons: {}", build_by_heapify(&values));
}

추가 케이스 힙 push/pop 재확인 해석

이 예제는 실행 시간을 재지 않고 비교 연산 수를 직접 셉니다.
그래서 환경 차이 없이 두 방식의 비용 차이를 안정적으로 볼 수 있습니다.
초기 데이터가 한 번에 있으면 보통 heapify가 유리하고, 스트림 입력이면 반복 push가 자연스럽습니다.

평균 시간복잡도: 반복 push O(N log N), heapify O(N)
최악 시간복잡도: 반복 push O(N log N), heapify O(N)
공간복잡도: O(N) (힙 저장 공간)

힙 운영 전 검토 체크리스트

힙 기반 로직을 운영에 올릴 때는 다음 항목을 확인합니다.

힙 크기 상한이 있는가
우선순위 동점 정책이 명시되어 있는가
빈 힙 접근 예외가 호출자에서 처리되는가
최대 힙 트릭(부호 반전)이 누락되지 않았는가

이 체크를 자동 테스트로 묶어두면 회귀 버그를 크게 줄일 수 있습니다. 또한 입력 규모가 커질수록 push/pop 호출 횟수 자체를 줄이는 설계가 더 큰 효과를 냅니다. 예를 들어 배치 병합이나 지연 평가를 결합하면 힙 연산 총량을 줄일 수 있습니다. 이 관점은 단순한 코드 미세 최적화보다 훨씬 큰 성능 이득을 주는 경우가 많습니다. 문제 규모가 커질수록 이러한 설계 차이는 더 크게 벌어집니다.

힙 상태 로그 실수 포인트

힙 구현/사용에서 자주 보는 실수입니다.

힙 배열을 정렬 배열로 오해함
빈 힙 pop 예외 처리 누락
최대 힙 구현에서 부호 반전 누락
우선순위 동점 처리 규칙 미정의

테스트는 동점 다수, 음수 값, 빈 입력 케이스를 반드시 포함해야 합니다.

힙 연산 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 선택 관점을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

연산	평균 시간	최악 시간	공간
`heappush`	`O(log N)`	`O(log N)`	`O(N)`
`heappop`	`O(log N)`	`O(log N)`	`O(N)`
최소값 조회	`O(1)`	`O(1)`	`O(N)`

전체 정렬과 힙 연산은 목적이 다르므로 같은 잣대로만 비교하면 안 됩니다.

heapify 구간 문제분석 체크 포인트

힙은 비교 가능 타입 간 혼합 입력에서 오류가 날 수 있습니다.
대량 데이터에서는 push/pop 횟수 자체를 줄이는 설계가 더 효과적일 수 있습니다.
성능 측정 시 결과 출력 비용을 분리해야 정확한 연산 시간을 얻습니다.
우선순위 큐와 힙 구현의 예외 정책을 API 문서에 명시해야 합니다.

힙 구현 전후 점검 목록

힙 방향(최소/최대)과 비교 함수를 코드에 명시했는가
heapify와 반복 삽입 중 요구사항에 맞는 빌드 방식을 선택했는가
힙 top 조회와 정렬된 출력의 차이를 분리해 이해했는가
반례(빈 힙, 중복 값, 음수)를 포함해 테스트했는가

힙 동작 검토 정리

힙의 본질은 부분 순서를 유지해 극값 접근을 빠르게 만드는 데 있습니다.
push/pop 복원 규칙을 정확히 이해하면, 우선순위 문제를 안정적으로 확장할 수 있습니다.

힙의 구조와 push/pop 동작 원리

목차