우선순위 큐와 힙은 뭘까?

23.1 도입

• 우선순위 큐
  • 선입선출이 아니고, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다.
  • 연결 리스트나 동적 배열로 구현 가능하다 O(n) 시간 소요되며 비효율적이다.
  • 힙을 통해 구현하는 것이 가장 적합하다.
• 힙
  • 가장 큰 또는 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리
  • O(lgN) 시간 소요

23.2 힙의 정의와 구현

• 특정한 규칙을 만족하는 이진 트리
• 대소 관계 규칙: 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다.
• 힙의 모양 규칙
  • 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
  • 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있어야 한다.

배열을 이용한 힙의 구현

• 트리에 포함된 노드의 개수만 알면 트리 전체의 구조를 알 수 있다.

배열을 이용한 힙

 

 

• 배열을 제일 위 왼쪽 끝부터 채웠다.
• 부모 노드의 왼쪽 노드는 배열의 홀수 index, 오른쪽 노드는 배열의 짝수 index인 규칙을 가지고 있다.

 

새 원소의 삽입

• 모양 규칙에 의해 새 노드는 항상 heap[] 의 맨 끝에 추가된다.
• 그리고 새 노드는 트리의 제일 밑 왼쪽부터 자신의 자리를 찾아간다.

 

최대 원소 꺼내기

• 힙의 모양 구조에 의하면 힙의 마지막에 있는 노드는 지우고 시작한다.
  • 리프 노드
• 마지막에 있는 원소는 루트에 덮어씌운다.
  • 부모-자식 간의 대소 관계만 취급하기 때문에 규칙을 어기는 것은 아니다.
  • 기존 루트의 자식인 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 원소와 맞바꾸는 작업을 트리의 바닥에 도달하거나, 두 자손이 모두 자기 자신 이하의 원소를 갖고 있을 때 까지 반복한다.

ref

• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략