Python에서 최대 힙 가져오기

Jesse John 2023년1월30일
  1. Python에서 숫자로 최대 힙 얻기
  2. Python에서 튜플을 사용하여 최대 힙 가져오기
  3. 참고문헌
Python에서 최대 힙 가져오기

힙은 우선순위 큐를 구현하기 위해 선택한 데이터 구조입니다. 이진 검색 트리와 달리 힙은 완전히 정렬되지 않습니다. 형제나 사촌 사이에는 명확한 순서가 없습니다.

Python에서 heapq 모듈은 힙 큐 알고리즘을 구현합니다. 그러나 heapq는 상위 노드의 값이 하위 노드 중 하나보다 작거나 같은 최소 힙 구현만 제공합니다.

메인 함수인 heappop()은 힙의 가장 작은 요소를 반환합니다.

이 기사에서는 heapq를 일부 사용자 정의 코드와 결합하여 Python에서 최대 힙 동작을 구현하는 방법에 대해 설명합니다.

Python에서 숫자로 최대 힙 얻기

숫자를 다룰 때 가장 일반적인 전략은 목록의 요소에 -1을 곱하는 것입니다. heapq 함수는 힙을 처리할 수 있습니다.

가장 작은 값을 팝한 후 최대값을 얻으려면 출력에 -1을 다시 곱해야 합니다.

예제 코드:

# import the heapq module.
import heapq

# Max Heap With Numbers

# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)

# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)

# Make the heap.
heapq.heapify(x_inv)

# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)

출력:

print(x)
[5, 4, 3, 6, 8, 7, 2, 1]

print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]

-1 * heapq.heappop(x_inv)
Out[8]: 8

-1 * heapq.heappop(x_inv)
Out[9]: 7

-1 * heapq.heappop(x_inv)
Out[10]: 6

Python에서 튜플을 사용하여 최대 힙 가져오기

숫자가 아닌 튜플을 사용하여 우선 순위 대기열을 구현하고 싶을 수 있습니다. Python의 튜플은 변경할 수 없으므로 우선 순위 번호에 -1을 곱하는 작업에 대한 도전입니다.

해결책은 먼저 각 튜플을 목록으로 변환하고, 이 하위 목록의 첫 번째 요소를 -1로 수정하고, 다시 튜플로 변환하고, 동시에 이러한 튜플을 사용하여 새 목록을 만드는 것입니다. 그런 다음 새 목록은 heapify()를 사용하여 힙으로 변환됩니다.

최대값을 팝하려면 힙에서 heappop()을 사용하고 튜플을 목록으로 변환하고 첫 번째 요소를 수정하여 양수 값을 얻은 다음 목록을 다시 튜플로 변환합니다.

예제 코드:

# Max Heap With Tuples

# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l

# Create an empty list to hold modified tuples.
l_max = []

# Populate the list with modified tuples.
for i in range(len(l)):
    j = list(l[i])
    j[0] = -1 * j[0]
    l_max.append(tuple(j))

# View the modified list.
l_max

# Create the min heap.
heapq.heapify(l_max)

# View the min-heap.
l_max

# Create a function that uses meappop and
# changes the number back to a positive value.


def maxpop(mh):
    l = list(heapq.heappop(mh))
    l[0] = -1 * l[0]
    return tuple(l)


# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)

출력:

l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]

l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]

heapq.heapify(l_max)

l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]

maxpop(l_max)
Out[19]: (7, 'D')

maxpop(l_max)
Out[20]: (6.5, 'E')

maxpop(l_max)
Out[21]: (5, 'B')

다른 필요한 힙 기능은 동일한 기술을 사용하여 구현할 수 있습니다.

참고문헌

자세한 내용과 예제는 파이썬의 heapq 모듈 문서를 참조하세요.

파이썬 개발팀은 최대 힙 기능을 구현하지 않기로 결정했습니다. 기능 요청과 응답은 여기에서 읽을 수 있습니다.

작가: Jesse John
Jesse John avatar Jesse John avatar

Jesse is passionate about data analysis and visualization. He uses the R statistical programming language for all aspects of his work.

관련 문장 - Python Heap