최대 힙 유지 새 항목을 삽입하는 동안 정렬

Question

모든 작업을 가능한 가장 효율적으로 구현하면서 숙제를 통해 은행 시스템을 구축했습니다.

프로그램 할 수 있습니다 내가 처음 3 것들에 대한 레드 - 블랙 트리 가기로 결정

1.add a new customer 
2.delete an existing customer 
3.find a customer 
4.print the customer with the highest balance. 
5.print all customers with a negative balance. 
6.deposit/withdraw money 

(O (로그 N)). 나는 4th와 5th에 관해서 확실하지 않다.

4 : 최대 힙을 유지하는 것에 대해 생각 했으므로 가장 부유 한 고객을 불러 오면 루트 노드 인 O (1) 만들 수 있습니다. 내 최대 힙 코드가 시도한 랜덤 배열 (목록)에서 작동합니다. 그러나이 특정 경우에, 나는 분명히 나중에 채워 져야하는 빈 배열로 시작합니다. insert 메서드를 최대 힙에 사용하면 정렬되지 않은 배열이됩니다 (). (기본적으로 나는 힙 빌딩을 건너 뜁니다.). 최대 힙 삽입 방법 :

dataArray.add(newCustomer); 
heapSize = dataArray.size(); 
int i = dataArray.size()-1; 
while(i > 1 && dataArray.get(getParentIndex(i)).getAccountBalance() < newCustomer.getAccountBalance()) 
{ 
    swap(dataArray, getParentIndex(i) , i); 
    i = getParentIndex(i); 
} 

5 : 나는 음의 균형을 가진 사람들의 연결리스트를하는 것에 대한 생각했다. 이렇게하면 인쇄 할 때 복잡성이 선형이됩니다. (RBTree는 마이너스 잔액이없는 고객이 있더라도 logN 비용이들 것입니다.) 그러나 고객을 삭제할 경우 해당 목록에서 고객을 찾아서 제거해야합니다 (RBTree 삭제 lgn + n 목록 삭제 = n * lgn)

Answer 1

나는 두 개의 이진 탐색 트리 (키는 고유 한 고객 ID)를 유지할 것이며, 하나는 음수 균형을, 다른 하나는 양수 균형을 유지하는 고객을위한 것입니다. 그리고 항상 가장 높은 균형을 가진 고객을 가리키는 포인터 richest.

모든 잔액이 변경 될 때 잔액의 부호가 변경되었는지 확인해야합니다. 그렇다면 한 트리에서 고객을 삭제하고 다른 트리에 추가하십시오.

그리고 현재 잔액이 잔액이 richest인지 확인하고 잔액이 더 높은 경우 현재 고객을 지정하십시오.

복잡성은 다음과 같습니다

1. insert to tree: O(log(n)) 
2. delete from tree: O(log(n)) 
3. binary search in two trees: O(log(n)) 
4. print the customer pointed by `richest`: O(1) 
5. in-order run on a binary search tree (the negative one): O(n) 
6. find costumer: O(log(n)) + possible deletions and insertions: still O(log(n)) 

Answer 2

그냥 @Nimrod 모라 그의 솔루션의 상단에 추가가 더 나은 average 및 amortized 시간 복잡성을 가지고, 당신은 Fibonacci-heap 데이터 구조 (참조 https://en.wikipedia.org/wiki/Fibonacci_heap 및 http://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf)를 사용하고 하나를 유지할 수 있습니다 고객에 대한 fib-max-heap (A max 포인터를 가지고있는) 그리고 당신이 할 수있는 모든 작업은 :

1. insert (lazily) a customer to the heap: O(1) 
2. delete any customer (or the customer with maximum balance) 
    from heap: O(log(n)) amortized 
3. search a customer in heap: O(log(n)) 
4. print the customer pointed by `max` pointer: O(1) 
5. in-order run on the heap and print only the -ve balances: O(n) 
6. deposit/withdraw money: O(1) amortized