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