Python의 heapq 모듈은 무엇입니까?

Python의 heapq 모듈은 무엇입니까?

---

나는 "heapq"를 시도 했고 내 기대치가 화면에서 보는 것과 다르다는 결론에 도달했다. 나는 그것이 어떻게 작동하고 어디에 유용 할 수 있는지 설명 할 누군가가 필요합니다.

2.2 단락 의 Python Module of the Week 책에서 정렬 이 작성되었습니다.

값을 추가하고 제거 할 때 정렬 된 목록을 유지해야하는 경우 heapq를 확인하십시오. heapq의 함수를 사용하여 목록에서 항목을 추가하거나 제거하면 낮은 오버 헤드로 목록의 정렬 순서를 유지할 수 있습니다.

여기에 내가하고 얻는 것이있다.

import heapq
heap = []

for i in range(10):
    heap.append(i)

heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heapq.heapify(heap)    
heapq.heappush(heap, 10)    
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heapq.heappop(heap)
0    
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?

heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

따라서 "힙"목록이 전혀 정렬되지 않은 것을 볼 수 있습니다. 실제로 항목을 더 많이 추가하고 제거할수록 항목이 더 복잡해집니다. 푸시 된 값은 설명 할 수없는 위치를 차지합니다. 무슨 일이야?

---

heapq모듈은 유지 힙 불변 정렬 된 순서의 실제 목록 개체를 유지와 같은 것이 아니다.

heapq문서 에서 인용 :

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리입니다. 이 구현을위한 배열을 사용 heap[k] <= heap[2*k+1]하고 heap[k] <= heap[2*k+2]모두를 k0에서 요소를 계산. 비교를 위해 존재하지 않는 요소는 무한한 것으로 간주됩니다. 힙의 흥미로운 속성은 가장 작은 요소가 항상 루트라는 것 heap[0]입니다.

즉 heap[0], 우선 순위 대기열에 적합한 가장 작은 요소를 찾는 것이 매우 효율적 입니다. 그 후, 다음 2 개의 값은 1 번째 값보다 크거나 같을 것이고 그 다음 4 개의 값은 '부모'노드보다 클 것이고 다음 8 개 값은 더 커질 것입니다.

문서 의 이론 섹션 에서 데이터 구조의 이론에 대한 자세한 내용을 읽을 수 있습니다 . 알고리즘을 일반적인 용어로 설명하는 MIT OpenCourseWare Introduction to Algorithms 과정에서이 강의를 볼 수도 있습니다 .

힙은 매우 효율적으로 정렬 된 목록으로 되돌릴 수 있습니다.

def heapsort(heap):
    return [heapq.heappop(heap) for _ in range(len(heap))]

힙에서 다음 요소를 팝하면됩니다. 사용 sorted(heap)파이썬의 종류에 의해 사용되는 TimSort 알고리즘은 힙에 이미 존재하는 부분 순서를 활용하므로, 그러나, 빠른 여전히해야합니다.

가장 작은 값에만 관심이있는 경우 힙을 사용하거나 n, 특히 지속적으로 해당 값에 관심이있는 경우 가장 작은 값에 관심이있는 경우 힙을 사용 합니다. 새 항목을 추가하고 가장 작은 항목을 제거하는 것은 값을 추가 할 때마다 목록을 재지 정하는 것보다 훨씬 효율적입니다.

---

책이 잘못되었습니다! 보여 주듯이 힙은 정렬 된 목록이 아닙니다 (정렬 된 목록은 힙이지만). 힙이란 무엇입니까? Skiena의 알고리즘 설계 매뉴얼을 인용하려면

힙은 우선 순위 큐 작업 삽입 및 추출-분을 효율적으로 지원하기위한 간단하고 우아한 데이터 구조입니다. 정렬 된 순서보다 약하고 (유지하는 것이 효율적일 수 있으므로) 임의의 순서보다 강한 (최소 요소를 빠르게 식별 할 수 있도록) 요소 세트에 부분 순서를 유지하여 작동합니다.

정렬 된 목록에 비해 힙 은 힙 불변 의 약한 조건을 따릅니다 . 정의하기 전에 먼저 상태를 이완하는 것이 유용한 이유를 생각하십시오. 대답은 약한 상태가 유지하기 더 쉽다는 것 입니다. 힙으로 덜 할 수 있지만 더 빨리 할 수 있습니다 .

힙에는 세 가지 작업이 있습니다.

1. 찾기-최소값은 O (1)입니다.
2. O (log n) 삽입
3. 최소 제거 O (log n)

Crucially Insert는 정렬 된 목록에서 O (n)을 능가하는 O (log n)입니다.

What is the heap invariant? "A binary tree where parents dominate their children". That is, "p ≤ c for all children c of p". Skiena illustrates with pictures and goes on to demonstrate the algorithm for inserting elements while maintaining the invariant. If you think a while, you can invent them yourself. (Hint: they are known as bubble up and bubble down)

The good news is that batteries-included Python implements everything for you, in the heapq module. It doesn't define a heap type (which I think would be easier to use), but provides them as helper functions on list.

Moral: If you write an algorithm using a sorted list but only ever inspect and remove from one end, then you can make the algorithm more efficient by using a heap.

For a problem in which a heap data structure is useful, read https://projecteuler.net/problem=500

---

There is some misunderstanding of the heap data structure implementation. The heapq module is actually a variant of the binary heap implementation, where heap elements are stored in a list, as described here: https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Quoting Wikipedia:

Heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices.

This image below should help you to feel the difference between tree and list representation of the heap and (note, that this is a max heap, which is the inverse of the usual min-heap!):

In general, heap data structure is different from a sorted list in that it sacrifices some information about whether any particular element is bigger or smaller than any other. Heap only can tell, that this particular element is less, than it's parent and bigger, than it's children. The less information a data structure stores, the less time/memory it takes to modify it. Compare the complexity of some operations between a heap and a sorted array:

        Heap                  Sorted array
        Average  Worst case   Average   Worst case

Space   O(n)     O(n)         O(n)      O(n)

Search  O(n)     O(n)         O(log n)  O(log n)

Insert  O(1)     O(log n)     O(n)      O(n)

Delete  O(log n) O(log n)     O(n)      O(n)

ReferenceURL : https://stackoverflow.com/questions/19979518/what-is-pythons-heapq-module