자료구조) Heap자료구조와 파이썬 Heapq 내장모듈

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

먼저, 글을 작성하기에 앞서 위 두 블로그의 글을 참고했다는 점을 알린다. Heap 자료구조를 공부하는데 큰 도움이 되었다.

 

힙 자료구조

- "우선 순위 큐"를 위해 만들어진 자료구조

- "완전 이진 트리(binary tree)의 일종이다.

- 여러개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

- 중복된 값을 허용해준다.

 

힙의 종류

- 최대 힙

부모 노드의 키값이 항상 자식노드의 키 값보다 크거나 같은 완전 이진 트리

- 최소 힙

부모 노드의 키 값이 항상 자식노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

 

 

 

 

내가 받은 느낌은 Sorting을 빠르게 하거나, 최댓값, 최솟값 혹은 n번째 최댓값 최솟값을 빠르게 찾아 줄 수 있는 자료구조인것 같다.

 

 

힙의 구현(파이썬 heapq 모듈)

힙에 원소 추가

import heapq
heap = []

#heapq는 자체적인 자료구조가 아닌 리스트를 통해 구현
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
# [1, 3, 7, 4]
# 가장 작인 1이 인덱스 0(최소 힙을 만들기 때문에 무조건 0번째 인덱스는 최소값이다.
# 인덱스 1(=k)에 위치한 3은 인덱스 3(2k+1)에 위치한 4보다 크므로 힙의 공식을 만족

 

힙에서 원소 삭제

print(heapq.heappop(heap))
#1
print(heap)
#[3,4,7]

#최소값인 1이 pop되어 리턴 되고, 그 다음으로 작았던 3이 인덱스 0으로 올라옴.

#최소값을 삭제하지 않고 얻기 위해서는
print(heap[0])

 

기존 리스트를 힙으로 변환

heap = [4,1,7,3,8,5]
heapq.heapify(heap)
print(heap)
#[1,3,5,4,8,7]

 

heap의 k번쨰 최소 / 최대 값 구하기

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

heap 정렬

 

import heapq

def heap_sort(nums):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)
  
  sorted_nums = []
  while heap:
    sorted_nums.append(heapq.heappop(heap))
  return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))