[자료구조] 우선순위 큐와 힙 / 최소 힙 / 최대 힙 / heap /

우선순위 큐

Queue 자료구조는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장

우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터 먼저 나온다.

 

힙 (Heap) 이란?

• Heap은 우선순위큐(priority queue)의 구현과 일치
• Heap은 완전이진트리 구조
• 최소 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다
• 최대 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 크거나 같다

최대 힙

파이썬 힙 함수

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop + 리턴. 비어 있는 경우 IndexError

1. 최소 힙

import heapq


# 오름차순 힙 정렬
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 result 에 추가
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result


array = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
res = heapsort(array)

for i in range(len(array)):
    print(res[i],end=' ')

# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

2. 최대 힙

import heapq


# 내림차순 힙 정렬
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 result 에 추가
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result


array = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
res = heapsort(array)

for i in range(len(array)):
    print(res[i],end=' ')

# 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

 

시간복잡도

push	pop
O(logN)	O(logN)
heap tree의 높이는 logN push 할 때 swap 하는 과정이 최대 logN 반복되서 O(logN)	heap tree의 높이는 logN pop 할 때 swap 하는 과정이 최대 logN 반복되서 O(logN)