今天讀了lucent中的PriorityQueue.java, 一個很巧妙的復雜度為log(n)的排序堆棧. 始終確保數組A[1...n]中: A[i]<A[2*i] & A[i] < A[2*i +1] 很容易推論出A[1]一定是最小數值, 并且每次put()和pop()至多移動log(n)個數值 真是好久沒接觸算法了:)
top()返回的是heap[1]的數值,但不移除,heap[1]永遠要求是最小的值
pop()會移出heap[1]的數值,而后把heap[size]的值移到heap[1],而后使用downHeap() 把heap[1]下移到適合位置
put(element)是往隊列尾部heap[size],也就是buttom追加
insert(element)類似put,區別在于如果數組已經填滿時,如果element比top大時,就把heap[1]的數值緩存element,再重新排序
upHeap() 表示尾部(buttom)heap[size]追加了一個數值,因此,需要把這個數up到對應的位置。
downHeap() 表示top,即heap[1]的數值變化了,把它下移到適合的位置。
adjustTop() 同downHeap()