[자료구조] 우선순위큐 & 힙(heap)

우선순위 큐

: 우선순위를 가진 항목들을 저장하는 큐

FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.

 

자료구조	삭제되는 요소
스택	가장 최근에 들어온 데이터 (LIFO)
큐	가장 먼저 들어온 데이터 (FIFO)
우선순위 큐	가장 우선순위가 높은 데이터

 

우선순위 큐도 동일하게 insert 연산, delete 연산이 가장 중요한 연산이다.

두가지로 구분이 되는데 1. 최소 우선순위 큐(가장 작은값 우선) 2. 최대 우선순위 큐(가장 큰값 우선)

 

우선순위큐 구현방법

• 배열 이용
• 연결리스트를 이용
• 히프(heap)이용

비교 표: 삽입과 삭제 연산의 시간 복잡도

구현 방법	삽입 시간 복잡도	삭제 시간 복잡도
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(n)
정렬된 연결 리스트	O(n)	O(1)
힙 (Heap)	O(log n)	O(log n)

설명:

1. **순서 없는 배열**:
   - **삽입**: 배열의 끝에 값을 추가하는 것이므로 O(1).
   - **삭제**: 값을 삭제하려면 배열을 순회하며 해당 값을 찾아야 하므로 O(n).

2. **순서 없는 연결 리스트**:
   - **삽입**: 새로운 노드를 리스트의 머리나 꼬리에 추가하는 것이므로 O(1).
   - **삭제**: 삭제하려는 노드를 찾으려면 리스트를 순회해야 하므로 O(n).

3. **정렬된 배열**:
   - **삽입**: 적절한 위치를 찾아 값을 삽입해야 하므로 O(n) (배열이 정렬된 상태를 유지해야 하므로 삽입 위치를 찾는 데 O(n)).
   - **삭제**: 값을 삭제하고, 배열을 재정렬해야 하므로 O(n).

4. **정렬된 연결 리스트**:
   - **삽입**: 정렬된 상태에서 적절한 위치에 삽입해야 하므로 O(n).
   - **삭제**: 이미 정렬된 상태에서 바로 삭제할 수 있기 때문에 O(1).

5. **힙 (Heap)**:
   - **삽입**: 힙의 끝에 값을 추가하고 힙 속성을 유지하기 위해 트리를 위로 이동시켜야 하므로 O(log n).
   - **삭제**: 루트 노드를 삭제하고 마지막 노드를 루트에 올린 뒤, 힙 속성을 유지하기 위해 트리를 아래로 이동시켜야 하므로 O(log n).

>> 연산과정에서 O(n) 일 때 시간이 오래 걸린다. 

>> 히프 연산과정은 O(log n)이므로 삽입 삭제시 동일하게 시간이 걸린다. (효율적)

결론:
- **힙**은 삽입과 삭제가 모두 **O(log n)** 으로 가장 효율적인 방법입니다.
- **순서 없는 배열**과 **순서 없는 연결 리스트**는 **삽입**이 빠르지만, **삭제**는 비효율적입니다.
- **정렬된 배열**과 **정렬된 연결 리스트**는 삽입이 비효율적이지만 삭제는 빠르게 처리할 수 있습니다.

 

히프(heap)

: 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리

• 최소 히프(min heap)
• 최대 히프(max heap)

1. **최소 우선순위 큐 (Min-Heap)**

: 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전이진트리
   - 최소 우선순위 큐에서는 **가장 작은 값**이 가장 높은 우선순위를 가집니다.
   - 즉, 루트 노드에는 **최솟값**이 위치하며, 이 값이 먼저 제거됩니다.
   - 예: 숫자 1, 3, 2가 있는 최소 우선순위 큐에서는 1이 먼저 나옵니다.

   - key(부모노드)<=key(자식노드)  : 최솟값 -> 루트

2. **최대 우선순위 큐 (Max-Heap)**

: 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전이진트리
   - 최대 우선순위 큐에서는 **가장 큰 값**이 가장 높은 우선순위를 가집니다.
   - 즉, 루트 노드에는 **최댓값**이 위치하며, 이 값이 먼저 제거됩니다.
   - 예: 숫자 1, 3, 2가 있는 최대 우선순위 큐에서는 3이 먼저 나옵니다.

   - key(부모노드)>=key(자식노드)  : 최댓값 -> 루트

 

히프의 높이

- n 개의 노드를 가지고 있는 히프의 높이는 O(log n), 히프는 완전이진트리이다(모든 노드가 두 자식 노드를 가질 수 있는 구조이다)

- 그러므로 힙의 높이는 노드의 개수에 따라 결정된다.

- 노드의 개수가 n일 때, 완전이진트리의 높이는 log n이다. 각 레벨 i에는 2의(i-1)승 개의 노드가 존재한다.( 이때 마지막 레벨의 개수는 다를 수 있음)

 

 

히프의 구현방법

- 배열을 이용한 구현 >> 완전이진트리이므로 각 노드에 번호를 매길 수 있음, 이 번호를 배열의 인덱스라고 생각하자

- 부모노드와 자식노드를 찾기 쉽다. >> 왼쪽 자식의 인덱스 = (부모인덱스)*2, 오른쪽 자식의 인덱스 = (부모인덱스)*2 +1임. 또한 부모의 인덱스 = (자식의 인덱스)/2 이다.

 

히프에서의 삽입

: 히프에서의 삽입은 새로운 노드를 신입사원이라고 생각하면 편하다. 먼저 새로운 것은 히프의 마지막 노드로 삽입한다. 

삽입한 뒤에 새로운 노드를 부모 노드(기존 사원)들과 교환해서 히프의 성질을 만족시킨다.

 

upheap 연산

- 새로운 키 k의 삽입 연산 이후에 히프의 성질이 만족되지 않을 수 도 있다. 히프의 성질을

 

 

**Upheap (또는 Heapify-up)**은 **힙(Heap)** 자료구조에서 사용되는 연산 중 하나로, **새로운 노드**를 삽입한 후 **힙의 성질**을 유지하기 위해 트리를 **위로**(root 방향으로) 재정렬하는 과정입니다. **힙의 성질**을 유지하려면, **최소 힙(Min-Heap)**에서는 부모 노드가 자식 노드보다 작아야 하고, **최대 힙(Max-Heap)**에서는 부모 노드가 자식 노드보다 커야 합니다.

### Upheap의 과정 (힙의 성질 유지)
1. **새로운 노드**를 힙의 **마지막**에 추가합니다.
2. 추가된 노드의 값이 부모 노드의 값보다 크거나 작을 수 있으므로, 부모 노드와 비교하여 **힙의 성질**에 맞게 트리를 조정합니다.
3. 추가된 노드가 부모 노드와의 관계에 따라 계속 **위로** 올라가게 되며, **힙의 성질**을 만족할 때까지 이 과정을 반복합니다.

### **최소 힙 (Min-Heap)**에서의 Upheap:
- **최소 힙**에서는 부모 노드가 자식 노드보다 **작아야** 합니다.
- 삽입한 노드가 부모 노드보다 작은 경우, 부모와 자식의 위치를 교환하여 트리의 성질을 유지합니다.

### **최대 힙 (Max-Heap)**에서의 Upheap:
- **최대 힙**에서는 부모 노드가 자식 노드보다 **커야** 합니다.
- 삽입한 노드가 부모 노드보다 큰 경우, 부모와 자식의 위치를 교환하여 트리의 성질을 유지합니다.

### **Upheap의 시간 복잡도**:
- **최악의 시간 복잡도**: 삽입 연산이 트리의 **높이**만큼 이동해야 하므로, **O(log n)**입니다. 여기서 **n**은 힙에 저장된 노드의 개수입니다.

### **Upheap 예시 (최소 힙)**:
예를 들어, **최소 힙**에 `5`가 추가되는 상황을 살펴봅니다.

- 초기 힙: `[3, 4, 7, 6]`
- `5`를 추가: `[3, 4, 7, 6, 5]`

이때 `5`는 부모 노드인 `7`보다 작기 때문에, `5`와 `7`을 교환합니다.

- 교환 후: `[3, 4, 5, 6, 7]`

이제 `5`는 부모 노드인 `3`보다 크므로, 더 이상 교환할 필요가 없습니다. 이로써 힙의 성질이 유지됩니다.

### **Upheap 예시 (최대 힙)**:
예를 들어, **최대 힙**에 `8`이 추가되는 상황을 살펴봅니다.

- 초기 힙: `[10, 9, 7, 5]`
- `8`을 추가: `[10, 9, 7, 5, 8]`

이때 `8`은 부모 노드인 `7`보다 크기 때문에, `8`과 `7`을 교환합니다.

- 교환 후: `[10, 9, 8, 5, 7]`

이제 `8`은 부모 노드인 `9`보다 작으므로, 더 이상 교환할 필요가 없습니다. 이로써 힙의 성질이 유지됩니다.

### 결론:
**Upheap**은 힙에 노드를 삽입할 때, **힙의 성질**을 유지하기 위해 **위로** 올라가며 트리 구조를 재조정하는 연산입니다. 이 연산은 **O(log n)**의 시간 복잡도를 가집니다.

 

 

downheap 알고리즘

downheap 알고리즘은 힙(heap) 자료구조에서 루트 노드를 제거한 후, 힙 속성을 복원하기 위해 사용하는 과정입니다.

다음 코는 최대 힙(max heap)을 기반으로 작성되었으며, 루트 노드를 삭제한 후 힙 속성을 유지하도록 트리 구조를 조정합니다.

 

//downheap 알고리즘
delete_max_heap(A)

//1. 초기화 및 삭제 과정
item <- A[1]; //루트노드 최대값 저장(반환값)
A[1] <- A[heap_size]; //가장 마지막요소를 다른 요소들과 비교하며 루트로 이동함
heap_size <-heap_size-1; //힙의 크기를 하나 줄임 >> 마지막 요소를 루트로 가져왔으므로 실제 힙의 크기는 하나만큼 줄어듦
i <- 2; //힙 트리의 왼쪽 자식 노드를 초기 탐색 위치로 지정(사용자 설정)
//초기 값으로 2를 할당한 이유: 루트노드(인덱스1)의 자식 노드부터 힙을 재정렬하기 위해 탐색을 시작
//i는 코드에서 현재 노드의 자식 노드 위치를 갱신하여 자기자신보다 작은 부모 노드와의 교환이 이루어진다

//2. 다운힙 과정
while i <= heap_size do //현재 노드의 인덱스가 힙의 범위를 넘지 않는 한 반복=
    if i < heap_size and A[i+1] > A[i] //i <heap_size조건 : 오른쪽 자식이 존재하는지 , A[i+1] > A[i] 조건: 오른쪽 자식이 왼쪽 자식보다 큰지
        then largest <- i+1; //오른쪽 자식
    else largest <- i; //왼쪽 자식
    // 오른쪽 왼쪽 둘중 더 큰 값을 가진 자식의 인덱스를 largest로 설정한다

    //3. 힙 속성 유지
    if A[PARENT(largest)] > A[largest]
        then break;  //부모노드가 더 크므로 종료
    else A[PARENT(largest)] <-> A[largest]; //부모노드가 더 작으므로 자식 노드와 교환
    i <- CHILD(largest); //자식 노드(largest)는 다음으로 이동할 노드 >> 힙 속성을 하위로 전파하여 재귀적으로 조정

return item; //item(최대값으로 저장됨) 루트노드를 반환한다

 

분석

1. 입력 및 시간 복잡도 

• 힙의 크기 n에 대해 트리의 높이는 log(n)
• downheap 과정은 최대 트리의 높이만큼 실행되므로 시간 복잡도는 O(log n)이다.

2. 핵심 내용

• 루트 노드를 제거하면서 발생한 힙 속성에 위배 발생
• 이를 하위 노드로 전파하며 수정
• 각 단계에서 부모 노드와 더 큰 자식 노드를 비교해 교환하면서 힙 속성 복원

3. 주요 조건

• 자식 노드 중 큰 값(largest)를 선택하는 과정이 중요하다
• 부모 노드가 자식보다 크면 종료

히프 정렬 알고리즘

- 정렬해야 할 n개의 요소들을 최대 히프에 삽입한다

- 한번에 하나씩 요소를 히프에서 삭제하여 저장

- 삭제되는 요소들은 값이 감소하는 순서(최대히프의 경우)

- 하나의 요소를 히프에 삽입하거나 삭제할 때 시간이 O(logn) 만큼 소요됨, 그 요소의 개수가 n개이므로 전체적으로 O(nlogn)시간이 걸린다