摘要:堆中位置的結(jié)點的父節(jié)點的位置為,子節(jié)點的位置分別是和一個結(jié)論一棵大小為的完全二叉樹的高度為用數(shù)組堆實現(xiàn)的完全二叉樹是很嚴格的,但它的靈活性足以使我們高效地實現(xiàn)優(yōu)先隊列。
Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 2 Section 4 優(yōu)先隊列
定義:當一棵二叉樹的每個結(jié)點都大于等于它的兩個子節(jié)點時,它稱為堆有序
相應地,在堆有序的二叉樹中,每個結(jié)點都小于等于它的父節(jié)點。從任意結(jié)點向上,我們都能得到一列非遞減的元素;從任意結(jié)點向下,我們都能得到一列非遞增的元素。特別的: 根結(jié)點是堆有序的二叉樹中的最大結(jié)點。
二叉堆表示法二叉堆:就是堆有序的完全二叉樹,元素在數(shù)組中按照層級存儲(一層一層的放入數(shù)組中,不用數(shù)組的第一個元素,因為0*2=0,遞推關(guān)系不合適)。下面簡稱堆。
堆中:位置K的結(jié)點的父節(jié)點的位置為 ?k/2? ,子節(jié)點的位置分別是 2k 和 2k+1
一個結(jié)論:一棵大小為N的完全二叉樹的高度為 ?lgN?
用數(shù)組(堆)實現(xiàn)的完全二叉樹是很嚴格的,但它的靈活性足以使我們高效地實現(xiàn)優(yōu)先隊列。
堆的算法我們用數(shù)組pq[N+1]來表示大小為N的堆,我們不使用pq[0]。
上浮(由下至上的堆有序)private void swim(int k) { while (k > 1 && less(k / 2, k)) { exch(k / 2, k); k = k / 2; } }下沉(由上至下的堆有序)
private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) j++; //找到子節(jié)點中更大的那個 if (!less(k, j)) break; //如果父結(jié)點比較大,則終止 exch(k, j);//如果父結(jié)點比較小,則把子節(jié)點中更大的那個jiaohuanshanglai k = j; } }MaxPQ 代碼
復雜度
插入:不超過lgN+1次比較
刪除最大元素:不超過2lgN次比較
簡易版
public class MaxPQ> { private Key[] pq; // heap-ordered complete binary tree private int N = 0; // in pq[1..N] with pq[0] unused public MaxPQ(int maxN) { pq = (Key[]) new Comparable[maxN + 1]; } public boolean isEmpty() { return N == 0; } public int size() { return N; } public void insert(Key v) { pq[++N] = v; //添加到最后 swim(N); //上浮 } public Key delMax() { Key max = pq[1]; // Retrieve max key from top.最大的為根結(jié)點 exch(1, N--); // Exchange with last item.和最后一個結(jié)點交換,并減小N pq[N + 1] = null; // Avoid loitering.刪除原來的最后一位 sink(1); // Restore heap property.下沉 return max; } // See above private boolean less(int i, int j) private void exch(int i, int j) private void swim(int k) private void sink(int k) }
完整版
添加resize功能
public class MaxPQ索引優(yōu)先隊列implements Iterable { private Key[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator comparator; // optional Comparator public MaxPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; N = 0; } public MaxPQ() { this(1); } public MaxPQ(int initCapacity, Comparator comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; N = 0; } public MaxPQ(Comparator comparator) { this(1, comparator); } public MaxPQ(Key[] keys) { N = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < N; i++) pq[i+1] = keys[i]; for (int k = N/2; k >= 1; k--) sink(k); assert isMaxHeap(); } public boolean isEmpty() { return N == 0; } public int size() { return N; } public Key max() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > N; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i <= N; i++) { temp[i] = pq[i]; } pq = temp; } public void insert(Key x) { // double size of array if necessary if (N >= pq.length - 1) resize(2 * pq.length); // add x, and percolate it up to maintain heap invariant pq[++N] = x; swim(N); assert isMaxHeap(); } public Key delMax() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key max = pq[1]; exch(1, N--); sink(1); pq[N+1] = null; // to avoid loiterig and help with garbage collection if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMaxHeap(); return max; } private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } } private boolean less(int i, int j) { if (comparator == null) { return ((Comparable ) pq[i]).compareTo(pq[j]) < 0; } else { return comparator.compare(pq[i], pq[j]) < 0; } } private void exch(int i, int j) { Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; } // is pq[1..N] a max heap? private boolean isMaxHeap() { return isMaxHeap(1); } // is subtree of pq[1..N] rooted at k a max heap? private boolean isMaxHeap(int k) { if (k > N) return true; int left = 2*k, right = 2*k + 1; if (left <= N && less(k, left)) return false; if (right <= N && less(k, right)) return false; return isMaxHeap(left) && isMaxHeap(right); } public Iterator iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private MaxPQ copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { if (comparator == null) copy = new MaxPQ (size()); else copy = new MaxPQ (size(), comparator); for (int i = 1; i <= N; i++) copy.insert(pq[i]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Key next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMax(); } } public static void main(String[] args) { MaxPQ pq = new MaxPQ (); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } }
增加索引
增加change, contains, delete方法
索引優(yōu)先隊列API 各方法的時間成本 IndexMinPQ 代碼簡易版
public class IndexMinPQ> implements Iterable { private int maxN; // maximum number of elements on PQ private int N; // number of elements on PQ private int[] pq; // binary heap using 1-based indexing private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i private Key[] keys; // keys[i] = priority of i public IndexMinPQ(int maxN) { this.maxN = maxN; keys = (Key[]) new Comparable[maxN + 1]; // 存一發(fā)原來的數(shù)組 pq = new int[maxN + 1]; // 這是二叉樹,比如1位置放的是想要記錄的是keys[3],但是記錄了3,即pq[1]=3 qp = new int[maxN + 1]; // 反過來,keys[3]放在哪里了呢?放在了樹的1位置, qp[3]=1 for (int i = 0; i <= maxN; i++) qp[i] = -1; } public void insert(int i, Key key) { if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue"); N++; qp[i] = N; // i放到了樹最后的位置N,通過原數(shù)組i找到樹中的位置N pq[N] = i; // 樹的最后位置N放了i,通過樹中的位置N找到原數(shù)組i keys[i] = key; //具體是什么 swim(N); //上浮 } private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); //在這里pq,qp都換好了 k = k/2; } } private void exch(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; //因為是逆運算 qp[pq[j]] = j; } public int delMin() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); int min = pq[1]; exch(1, N--); sink(1); qp[min] = -1; // delete keys[min] = null; // to help with garbage collection pq[N+1] = -1; // not needed return min; } public void changeKey(int i, Key key) {//改的是原來的數(shù)組 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); keys[i] = key; swim(qp[i]); //可能往上 sink(qp[i]); //可能往下 } }
完整版
public class IndexMinPQ> implements Iterable { private int maxN; // maximum number of elements on PQ private int N; // number of elements on PQ private int[] pq; // binary heap using 1-based indexing private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i private Key[] keys; // keys[i] = priority of i public IndexMinPQ(int maxN) { if (maxN < 0) throw new IllegalArgumentException(); this.maxN = maxN; keys = (Key[]) new Comparable[maxN + 1]; pq = new int[maxN + 1]; qp = new int[maxN + 1]; for (int i = 0; i <= maxN; i++) qp[i] = -1; } public boolean isEmpty() { return N == 0; } public boolean contains(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); return qp[i] != -1; } public int size() { return N; } public void insert(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue"); N++; qp[i] = N; pq[N] = i; keys[i] = key; swim(N); } public int minIndex() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } public Key minKey() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return keys[pq[1]]; } public int delMin() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); int min = pq[1]; exch(1, N--); sink(1); assert min == pq[N+1]; qp[min] = -1; // delete keys[min] = null; // to help with garbage collection pq[N+1] = -1; // not needed return min; } public Key keyOf(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); else return keys[i]; } public void changeKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); keys[i] = key; swim(qp[i]); sink(qp[i]); } public void change(int i, Key key) { changeKey(i, key); } public void decreaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key"); keys[i] = key; swim(qp[i]); } public void increaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key"); keys[i] = key; sink(qp[i]); } public void delete(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); int index = qp[i]; exch(index, N--); swim(index); sink(index); keys[i] = null; qp[i] = -1; } private boolean greater(int i, int j) { return keys[pq[i]].compareTo(keys[pq[j]]) > 0; } private void exch(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; qp[pq[j]] = j; } private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && greater(j, j+1)) j++; if (!greater(k, j)) break; exch(k, j); k = j; } } public Iterator iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private IndexMinPQ copy; // add all elements to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { copy = new IndexMinPQ (pq.length - 1); for (int i = 1; i <= N; i++) copy.insert(pq[i], keys[pq[i]]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Integer next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMin(); } } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66536.html
摘要:算法圖示代碼復雜度時間初始化優(yōu)先隊列,最壞情況次比較每次操作成本次比較,最多還會多次和次操作,但這些成本相比的增長數(shù)量級可忽略不計詳見空間 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 4 Section 3 最小生成樹 定義 樹是特殊的圖 圖的生...
摘要:相關(guān)操作就是判斷的不等號符號改反,初始值設(shè)為負無窮副本的最短路徑即為原圖的最長路徑。方法是同上面一樣構(gòu)造圖,同時會添加負權(quán)重邊,再將所有邊取反,然后求最短路徑最短路徑存在則可行沒有負權(quán)重環(huán)就是可行的調(diào)度。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter ...
摘要:只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運行,將頂點按照逆后序方式壓入棧中顯然,這個過程作用在有向無環(huán)圖上得到的就是一個拓撲排序作用在非上得到的是一個偽拓撲排序第二步在原圖上按第一步的編號順序進行。等價于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...
摘要:邊僅由兩個頂點連接,并且沒有方向的圖稱為無向圖。用分隔符當前為空格,也可以是分號等分隔。深度優(yōu)先算法最簡搜索起點構(gòu)造函數(shù)找到與起點連通的其他頂點。路徑構(gòu)造函數(shù)接收一個頂點,計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...
摘要:離心率計算題目釋義計算點的離心率,圖的直徑,半徑,中心計算圖的圍長定義點的離心率圖中任意一點,的離心率是圖中其他點到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點。改動離心率計算,在遍歷中增加的賦值即可。 離心率計算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...
閱讀 2888·2021-11-15 11:39
閱讀 1513·2021-08-19 10:56
閱讀 1093·2019-08-30 14:12
閱讀 3731·2019-08-29 17:29
閱讀 719·2019-08-29 16:21
閱讀 3417·2019-08-26 12:22
閱讀 1515·2019-08-23 16:30
閱讀 1015·2019-08-23 15:25