두 바이너리 힙 비교 및 ​​키, 값 쌍을 추적하십시오.

Question

저는 바이너리 힙 사용자 지정 구현 작업 중입니다. 최소 및 최대 힙이 필요하므로 "판매 - 구매"입찰 시스템을 만들 수 있습니다.

제 문제는 새로운 제안 (판매 또는 구매)이 들어올 때 구매가있을 때 "사람"이 힙에서 빠져 나와 그 목록을 추적해야한다는 것입니다. 바이너리 힙에서 Keys (이름)를 어떻게 추적 할 수 있는지 궁금합니다.

예를 들어 외부 클래스에서 나는 이와 같은 것을 가지고 있습니다.

public class OuterClass{ 
    public static HashMap<String, Integer> buyers = new HashMap<>(); 
    public static HashMap<String, Integer> sellers = new HashMap<>(); 

    public static BHeap<String, Integer> buyHeap = new BHeap<>(); 
    public static BHeap<String, Integer> sellHeap = new BHeap<>(); 
    //etc... 
} 

내 바이너리 힙 구현에서 나는 이와 같은 것을 가지고있다.

public class BHeap <K extends Comparable<? super K>, V extends Comparable<? super V>> { 
    protected ArrayList<K> keys = new ArrayList<>(); 
    protected ArrayList<V> values = new ArrayList<>(); 
    //do heap stuff 
} 

내가 일치하는 항목을 찾을 때까지 내가 터지는 갈 두 힙을 비교하고 (즉, 가격> = 판매 가격을 구입입니다). 하지만 어떻게 내가 (KEY)가 판매 사람을 추적하고 구입 할, 내가 돌아갈 수 유일한 정보는 VAL 때

Answer 1

pop() 또는 peek()(returns top element)을하고 다음 함수가 KEY되지에게 값을 반환 (그러나 팝업에 않았는데 솔루션입니다() 둘 ​​다를 제거하십시오). 그런 다음 외부 클래스에서 HashMap에서 일어나는 일을 추적합니다 (중복 될 수 있지만 다른 일을하는 것이 좋습니다)

또 다른 해결책은 ArrayList 자리 표시자가 "Person"또는 "Node ". 나는 실제로

class Node<K, V extends Comparable<? super V>>{ 
    Node<K, V> lchild = null, rchild = null, parent = null; 
    V value; 
    K key; 
} 

과 나무 기반의 솔루션을 선택했다했지만 그것은 배열 구현

수 있도록 특별히 요청 된