1. 도입

트리와 밀접하게 연관된 다른 자료 구조.
우선순위 큐: 큐처럼 순서대로 기다리고 있는 자료들을 저장하는 자료 구조.
BUT 우선순위가 가장 높은 자료가 가장 먼저 꺼내짐(큐와 다른 점)

구현 방법?

균형 잡힌 이진 트리 사용하면 원소들을 우선순위로 정렬해 두면 최대 원소를 찾아 삭제하는 일과 새 원소를 삽입하는 일을 모두 O(logn) 시간에 할 수 있음.

균형 잡힌 이진 트리보다 더 단순한 구조: 힙(heap)

힙: 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리. 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(logN) 시간에 수행 가능. 실제 힙을 사용하면 우선순위 큐 아주 쉽게 구현 가능.

2. 힙의 정의와 구현

힙은 특정한 규칙을 만족하도록 구성된 이진 트리. 단순히 최대 원소를 가능한 한 빠르게 찾을 수 있는 방법으로 설계됨.

힙의 대소 관계 규칙

힙에서 대소 관계 규칙은 부모 자식 관계에만 적용됨(↔ 이진 검색트리)

왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 X
⇒ 트리에서 가장 큰 원소는 항상 트리의 루트에 들어감(힙의 목적에 잘 부합)

BUT 이진 검색트리에서 트리의 구조를 제약한 것처럼, 트리의 구조가 한쪽으로 기울어져 속도를 느리게 하는 걸 방지하기 위해 힙에서도 트리의 구조에 제약이 있음.

힙의 모양 규칙

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함.
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 함.

따라서 힙의 높이는 logN임

배열을 이용한 힙의 구현

힙의 노드들은 배열의 원소들과 일대일 대응하는 것을 알 수 있음.

즉,

• A[i]에 대응 노드의 왼쪽 자손 = A[2*i-1]
• A[i]에 대응 노드의 오른쪽 자손 = A[2*i+2]
• A[i]에 대응 노드의 부모 = A[(i-1)/2]에 대응(여기서 나눗셈 결과는 내림)

새 원소의 삽입

힙의 모든 조건을 유지하면서 새 원소를 삽입할 수 있는 방법은?

루트부터 시작해 새 원소의 위치를 찾아보자. 우선 루트가 가진 원소와 새 원소를 비교하자. 대소 관계 규칙을 만족 위해서는, 둘 중 더 큰 원소가 루트를 차지하고 다른 원소가 아래로 밀려내려가야 함.

밀려내려가는 원소: 어느 서브트리?

1. 모양 규칙을 먼저 만족

   즉, 새노드는 항상 heap[]의 맨 끝에 추가. 힙의 대소 관계 속성은 일단 무시, 이 위치에 새 노드를 추가해서 모양 규칙을 만족.

2. 이후 대소 관계 속성 만족

   마지막에 추가한 새 원소를 자신의 부모 노드의 원소와 비교하고 부모 원소가 작다면 두 원소의 위치를 바꿈. 새 원소가 더 크거나 같은 원소를 가진 부모 노드의 원소를 만나거나 루트에 도달할 때까지 반복하자.

• 즉, 연어가 강물 거슬러 올라가는 모양을 연상하면 될 듯.

최대 원소 꺼내기

꺼내는 것은 쉬운데, 이후 힙 모양은 어떻게 재구성해야 하나?

1. 모양 규칙 만족

   힙의 마지막에 있는 노드를 우선 빼내고(어차피 이 자리는 없어질 거임), 그 원소를 루트의 노드에 덮어 씌움.

2. 대소 관계 속성 만족

   원래 루트의 두 자식 중 큰 쪽이 루트에 올라와야 함. 따라서 두 자식 노드의 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 노드와 맞바꿈.

이 작업을 트리의 바닥에 도달하거나 두 자손이 모두 자기 자신 이하의 원소를 갖고 있을 때까지 반복.

다른 연산들

• 힙을 만드는 연산
• 힙 정렬
• 우선순위 큐 구현

3. 문제: 변화하는 중간 값

한 수열의 중간 값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 (3,1,5,4,2}를 정렬했을 때가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간 값이라고 정의하도록 합시다. 한 수열의 중간 값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간 값을 계산하는 프로그램 을 작성하세요 . 예 를 들 어 3 , 1，5 , 4 , 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순 서 로 변 화 합 니 다 .

풀이 방법

[이진 검색트리 사용X하는 경우]

숫자들을 오름차순으로 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣는다.

만약 수열의 길이가 홀수: 최대 힙에 숫자를 하나 더 넣는다.

1. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 크다.
2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다.

이제 수열의 중간 값은 항상 최대 힙의 루트에 있게 됨.

새 숫자가 추가되는 경우: 둘 중 한 힙에 숫자를 추가해서 1번을 만족시키고 2번이 만족하지 않으면 최대힙의 최대 원소와 최소 힙의 최소 원소를 맞바꿈.
즉 새 숫자가 추가되어도 O(1)로 힙의 구조는 변형됨.