힙 Heap 개념,우선순위 큐를 이용한 구현 (python)과 성능 비교, 힙 정렬, 상향식 힙 생성, 응용 문제

1. 힙 Heap

내부 노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리

• 힙순서 (heap-order) : 루트를 제외한 모든 내부 노드 v

key(v) >= key(parent(v))

• 모든 노드의 경우, 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같아야 한다.
• 완전이진트리 (complete binary tree) : 힙의 높이 h
  • i = 0, ..., h-1에 대하여
  • 깊이 i인 노드가 $2^i$개 존재
  • 깊이 h-1에서 내부노드들은 외부노드의 왼쪽에 존재
  • 즉, 진행순서 : Root - L - R
  • ⇒ 힙의 마지막 노드는 깊이 h-1의 가장 오른쪽 내부 노드

• n개의 키를 저장한 힙의 높이 = O(logn)

2. 힙을 이용한 우선순위 큐 구현

• 각 내부노드에 key-value 쌍을 저장
• 마지막 노드의 위치를 변수로 관리

• 힙에 키 k를 삽입

1. 삽입 노드 z 위치 찾기 (완전이진트리 유지) → 새로운 마지막 노드를 찾는다.
2. k를 z에 저장한 후 expandExternal(w)작업 (외부노드 생성)으로 z의 내부노드로 확장한다.
3. 힙순서 속성을 복구한다.

• upheap
  • 마지막 외부 노드에 삽입된 노드의 키 값이 힙 순서 속성을 위배하는 경우 upheap으로 해당 노드로부터 상향 경로를 따라가며 k의 위치를 교환해준다.
  • k가 루트에 도달하거나 부모의 키가 k보다 작거나 같은 위치에 도달하면 정지한다.
  • O(logn)
• 삽입 알고리즘

• 외부 노드 만드는 알고리즘

삭제 removeMin

• 우선순위 큐 ADT의 메소드 removeMin은 힙으로부터 루트 키를 삭제하는 것이다.

1. 루트 키를 마지막 노드 w의 키로 대체
2. reduceExternal(z) 작업으로 w와 그의 자식들을 외부노드로 축소
3. 힙 순서 속성 복구

• downheap
  • 루트 키를 마지막 노드의 키로 대체한 후, 힙 순서 속성이 위배될 수 있다.
  • 루트가 된 w의 하향 경로를 따라 키를 교환하며 힙 순서 속성을 복구한다.
  • 탈출 조건 : 키가 마지막 노드 또는 자식의 키가 자신보다 크거나 같은 경우에 도달하면 정지한다. (작은 값일수록 상위 위치에 배치)
  • O(log n)
• 삭제 알고리즘

마지막 노드 갱신 작업

• O(logn)개의 노드를 순회하며 찾는다 (advanceLast)
• 삽입의 경우 마지막 노드에서 하나 오른쪽 노드를 찾아야 한다.
  
  • 현재 노드가 오른쪽 자식이면 부모노드로 이동
  • 현재 노드가 왼쪽 자식이면 오른쪽 자식으로 이동
  • 현재 노드가 내부노드이면 왼쪽 자식으로 이동
   

• 삭제의 경우 삽입과 반대 방향으로 수행 (retreatLast)
• ==루트 노드를 지우는 과정과 같음

3. 힙 구현과 성능

배열에 기초한 힙 구현

• n 개의 키를 가진 힙을 크기 n의 배열을 사용하여 표현
• 노드 i : 왼쪽 자식 2i, 오른쪽 자식, 2i+1, 부모 i
• 링크를 사용하지 않고 인덱스로 부모 자식 관계를 표현
• → 0번 노드는 사용하지 않는다.
• 마지막 노드의 인덱스는 항상 n
• insertItem은 n+1 위치에 삽입
• removeMin은 n에 있는 노드 삭제
• 공간 낭비가 없다.

연결리스트에 기초한 힙 구현

• 배열로 구현하는게 훨씬 간단해서 권장된다.

4. 힙 정렬

• 힙을 사용하여 구현된 n개의 항목을 우선순위 큐를 사용하여 정렬하는 것
• 공간 소요  O(n)
• insert, remove 시간 소요 O(logn)
  • n 개의 원소로 이루어진 리스트를 $O(nlogn)$ 시간에 정렬 가능
  • 선택 정렬, 삽입 정렬보다 훨씬 빠르다.
• 알고리즘

Alg heapSort(L)
		input list L
		output sorted list L
1. H <- empty heap
2. while (!L.isEmpty())
		k<- L.remove(L.first())
		H.insertItem(K)
	=> O(logn)
3. while (!H.isEmpty())
		k<-H.removeMin()
		L.insertLast(k)
	=> 2번을 n번 
4. return 

5. 제자리 힙 정렬

• 공간 사용을 줄인다.
• 정렬되어야 할 리스트가 배열로 주어진 경우에만 적용
• 알고리즘

Alg inPlaceHeapSort(A)
		input array A of n keys
		output sorted array A
1. buildHeap(A)
2. for i <- n downto 2
		A[1] <-> A[i]
		downHeap(1,i-1)
3. return


Alg buildHeap(A)
		input array A of n keys
		output heap A of size n
1. for i <- 1 to n
		insertItem(A[i])
2. return 


Alg downHeap(i,last)
		input index of A representing 
					a maxheap of size last
		output none
1. left <- 2i
2. right <- 2i+1
3. if(left>last)
		return   // 루트 값에 도달할때까지 재귀호출
4. greater <- left
5. if (right <= last)
			if (key(A[right]) > key(A[greater])
					greater <- right
6. if (key(A[i]) >= key(A[greater]))
			return
7. A[i] <-> A[greater]
8. downheap(greater, last)

 

6. 상향식 힙 생성

• 시간 소요를 줄인다.
• 처음 배열에서 루트값을 뺴오는 작업을 반복하면서 heap을 생성하는 작업을 할때,
• n 번의 연속적인 insertItem 작업을 하여 $O(nlogn)$ 시간 소요
• 힙에 저장되어야 하는 모든 키들이 주어진 경우, $O(n)$ 시간이 소요되는 상향식 힙 생성 방식 사용 가능

buttom-up heap construction

• logn 단계만을 사용하여 주어진 n 개의 키를 저장하는 힙 생성 가능
• i 단계에서 각 $2^i -1$개의 키를 가진 두개의 힙을 $2^i+1-1$개의 키를 가진 힙으로 합병
• 재귀 버전 알고리즘

Alg buildHeap(L)
		input list L sorting n keys
		output heap T sorting the keys in L
1. if (L.isEmpty())
			return empty heap
		// 리스트가 빌때까지 아래 과정을 반복하며 
			 리스트를 쪼개 트리를 만들고 heap화하고 합병
2. Remove the first key k from L
		// 리스트의 첫번째 키를 꺼내 그 값을 기준으로
				L1과 L2고 나눙 T1 T2 트리로 만든다. 
3. Split L into two sublists -> L1 & L2
4. T1 <- buildheap(L1)
5. T2 <- buildheap(L2)
6. Create a binary tree T 
			with root r sorting k
					 left subtree T1
					 right subtree T2
7. downHeap(r)
8. return T

비재귀적 상향식 힙 생성

• 정렬할 리스트가 배열로 주어진 경우에만 적용 가능하다.
• 내부 노드를 왼쪽 자식으로 가지는 가장 깊은 오른쪽 내부노드에서 시작하여 루트로 향하며 반복 수행한다.
• 시작 노드 : n/2
• 단독 내부 노드는 이미 정렬되어 있기 때문에 n/2부터 시작한다.

• 알고리즘

Alg buildHeadp(A)
		input array A of n keys
		output heap A of size n
1. for i <- [n/2] down to 1(root)
					downHeap(i,n)
2. return 

상향식 힙 생성의 성능

• 상향식 힙 생성 : $Θ(n)$

7. 응용문제

7.1 대화식 프로그램

• 순차힙 - 배열 사용
• 최대힙
• → 삭제시 최대값 삭제
• 원소 생략하고 키만 저장
• 인덱스 0 번은 비워둔다
• 중복키는 존재하지 않는다.
• in-place 방식
• 배열 크기 100 으로 설정
• 키 입력될 때마다 즉시 삽입
• 힙의 크기가 0이면 p
• 그냥 아무것도 출력하지마!
• 초기 인덱스는 항상 n+1
• 조건 및 입출력 예시

• 내가 푼 알고리즘 source code

class Heap:
    def __init__(self):
        self.array = [0,None]
        
    def insertItem(self,data):
        assert len(self.array)<100
        
        if self.array[1] ==None:
            self.array[1]=data
            
        else:
            self.array.append(data)
                    
        pointer = self.array[-1]
        self.upHeap(pointer)
        return 0
        
    def upHeap(self,pointer):
        if pointer ==self.array[1]:
            return

        pointer_index = self.array.index(pointer)
        if pointer < self.array[pointer_index//2]:
            return 
        
        # 부모 & pointer swapping
        self.array[pointer_index]=self.array[pointer_index//2]
        self.array[pointer_index//2] = pointer
        self.upHeap(self.array[pointer_index//2])
    
    def removeMax(self):
        root = self.array[1]
        if len(self.array)==2:
            self.array =[0,None]
            return root
        
        temp = self.array[-1]
        self.array.remove(root)
        self.array.remove(0)
        self.array.remove(temp)
        self.array = [0,temp] + self.array
        self.downHeap(self.array[1])
        return root
        
    def downHeap(self,pointer):
        assert pointer in self.array

        pointer_index = self.array.index(pointer)
        if (len(self.array)<=pointer_index*2)& \
            (len(self.array)<=pointer_index*2+1):
                return
            
        bigger = self.array[pointer_index*2]

        if (len(self.array)>pointer_index*2+1):
            if self.array[pointer_index*2+1] > bigger:
                bigger = self.array[pointer_index*2 +1]
                
        if pointer > bigger:
            return 
        
        bigger_index = self.array.index(bigger)
        
        self.array[pointer_index]=self.array[bigger_index]
        self.array[bigger_index] = pointer
        self.downHeap(self.array[bigger_index])
    
    def printData(self):
        for data in self.array[1:]:
            print(data,end=' ')
        print()
    
# i,d,p,q 네 가지 명령
H = Heap()

while True:
    order = input().split()
    if order[0] == 'i':
        print(H.insertItem(int(order[1])))

    elif order[0] == 'd':
        print(H.removeMax())

    elif order[0] == 'p':
        H.printData()
    elif order[0] == 'q':
        break
    else:
        break

7.2 상향식 힙 생성

• 내가 푼 알고리즈 source code

class Heap2:
    def __init__(self):
        self.list = [0, None]

    def downHeap(self, i, n):
        bigger = i
        left = 2*i
        right = 2*i+1
        #print("bigger = %d left = %d right = %d" %(bigger, left, right))
        if left <= n and self.list[left] > self.list[bigger]:
            bigger = left
        if right <= n and self.list[right] > self.list[bigger]:
            bigger = right
            #print("bogger = %d" %(self.list[bigger]))
        if bigger != i:
            self.list[i], self.list[bigger] = self.list[bigger], self.list[i]
            self.downHeap(bigger, n)

    def insert(self, keys, n):
        for i in keys:
            if self.list[1] == None:
                self.list[1] = int(i)
            else: 
                self.list.append(int(i))
        
        for i in range(n//2, 0, -1):
            self.downHeap(i, n)

    def print(self):
        for i in self.list[1:]:
            print(i, end=" ")
        print()
  

h = Heap2()
n = int(input())
keys = input().split()
h.insert(keys, n)
h.print()

---

References

• 성균관대학교 안용학 교수님 2020-2 <데이터사이언스와 컴퓨팅2 (알고리즘) > 수업을 듣고 정리한 내용입니다.