보통 큐는 배열이나 연결 리스트 등으로 구현하는 것이 일반적이다. 그러나, 그렇게 구현하게 된다면,
같은 문제가 발생한다.
따라서 우리는 우선순위 큐를 만들 때 힙 ( Heap ) 을 사용하여 개발한다.
힙 이란 완전 이진 트리의 일종으로, 여러 값중에 최대값이나 최솟값을 찾아내도록 만들어진 자료구조이다. 반 정렬상태 ( 느슨한 정렬 상태 ) 를 유지한다는데, 딱히 큰 의미는 없고, 큰 값이 상위 레벨, 작은 값이 하위 레벨에 있다는 의미이다.
또한 힙 트리에서는 중복된 값을 허용하는데, 이진 탐색 트리에서는 중복된 값을 허용하지 않는다.
힙에는 최대 힙( Max heap ) / 최소 힙( Min heap ) 2가지가 있는데, 각각 키 값이 부모의 값 이상이거나 이하인 힙이다.
힙은 평범하게 배열로 구분되며, 배열의 첫 인덱스인 0 은 사용하지 않고 구현한다고 한다. 힙에서 부모 노드와 자식 노드의 관계는 다음과 같다.
삽입은 다음처럼 구현한다.