힙은 부모와 자식 사이의 우선순위 조건을 유지하는 트리 기반 자료구조이다. 최소 힙은 부모 키가 자식 키보다 크지 않도록 유지한다.
원리
최솟값은 루트에서 찾지만 다른 모든 원소가 정렬된 상태는 아니다. 우선순위 큐의 구현에 사용하며, 메모리 할당 영역을 뜻하는 힙과는 다른 개념이다.
예시
대기 작업의 실행 시각을 키로 쓰면 가장 이른 작업을 루트에서 꺼낼 수 있다. 새 작업을 넣은 뒤 부모와 비교하며 위치를 조정한다.
주의할 점
아무 값이나 검색하는 연산은 빠르다고 보장할 수 없다. 같은 우선순위의 순서를 유지하려면 별도의 순번을 키에 포함하는 등 추가 규칙이 필요하다.