파이썬 같은 해시 힙 구현

Question

내가 스트림 데이터가오고 있고, 나는 힙 (우선 순위 큐)에 하나씩 밀어을 유지하고는, 그 결과 힙 보인다 (예 : 변경 (a, 1)에서 (a, 2) 또는 삭제 (c, 7)) 시간을 계속해서 항목을 업데이 트하십시오. 비효율적으로 힙의 항목을 찾아서 제거하기 위해 해시 테이블에 저장된 힙의 모든 항목의 위치를 ​​사용하여 해시 테이블을 구성하려고합니다.

항목을 업데이트 할 때마다 해시 테이블을 사용하여 해당 테이블을 찾고 쉽게 변경할 수 있으며 해시 테이블의 모든 항목의 위치를 ​​업데이트합니다.

같은 질문이 게시물에 요청하고있다 : 코드를 C++로 How to implement O(1) deletion on min-heap with hashtable을 다음과 같이

template<typename state, typename CmpKey, class dataStructure> 
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index) 
{ 
     if (index == 0) return false; 
     int parent = (index-1)/2; 
     CmpKey compare; 

     if (compare(elements[theHeap[parent]], elements[theHeap[index]])) 
     { 
       // Perform normal heap operations 
       unsigned int tmp = theHeap[parent]; 
       theHeap[parent] = theHeap[index]; 
       theHeap[index] = tmp; 
       // Update the element location in the hash table 
       elements[theHeap[parent]].openLocation = parent; 
       elements[theHeap[index]].openLocation = index; 
       HeapifyUp(parent); 
       return true; 
     } 
     return false; 
} 

을 나는 누군가가 나에게 아이디어를 설명하거나 파이썬 버전 코드를 제공 할 수 있는지 궁금, C++와 약간의 경험을 가지고 그런 구현의?

Answer 1

제 쌍안의 첫 번째 항목이 키 역할을하고 두 번째 항목이 데이터 페이로드 역할을한다는 것을 이해했습니다. 그런 다음 다른 방법으로 접근 방식을 제안합니다. 다소 비슷하지만 this answer과 비슷합니다.

1. 는 해시 테이블의 데이터 세트의 작은 전류 키를 유지하기위한 보조 데이터 구조를 저장 될 데이터와 최소 힙 기본 데이터 구조하자.

2. 새 항목 삽입 : 데이터를 해시 테이블과 최소 힙에 모두 추가하십시오.

3. 주어진 키의 값을 업데이트하십시오. 해시 테이블의 값만 업데이트하십시오.

4. 주어진 키를 사용하여 항목을 삭제하십시오. 해시 테이블에서만 주어진 키를 가진 항목을 삭제하십시오.

5. 가장 작은 키에 액세스 : 힙의 맨 위에있는 요소가 해시 테이블에없는 경우 삭제하십시오. 최상위 키가 해시 테이블에 나타날 때까지 반복하십시오.