[python] 힙(Heap) - heapq

💥 힙 자료구조

 

• 데이터를 정렬된 상태로 저장하기 위해 사용하는 파이썬 heapq
• 최대, 최솟값을 가져 올때 많이 사용

 

💥 힙 함수

 

1. heap 생성

heap = []  

 

2. heap 원소 추가

heapq.heappush(heap,4)

 

3. heap 원소 삭제 , 가장 작은 원소 삭제 후 그 값 리턴 

heapq.heappop(heap)

 

4. 최솟값 삭제 하지 않고 얻기

heap = [0]  

 

5. 기존 리스트를 힙으로 변환

heapq.heapify(heap)

 

import heapq
heap = []


# 힙 원소 추가
heapq.heappush(heap,4)
heapq.heappush(heap,1)
print(heap)

>>> [4,1]


# 힙 원소 삭제
print(heapq.heappop(heap))
print(heap)

>>> 1
>>> [4]


#최솟값 삭제 하지 않고 얻기
print(heap[0])

>>> 4


# 기존 리스트를 힙으로 변환
heap = [4,5,6,2,1]
heapq.heapify(heap)
print(heap)

>>>[1,2,4,5,6]

 

 

💥 힙 정렬

 

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,8,1,2,6,5]))

>>>[1,2,4,5,6,8]