アルゴリズム導論Java実装-優先順位行列(6.5章)
優先列は、スタックデータ構造の典型的な応用である。優先順位の行列の典型的なアプリケーションは、現在の優先順位が最も高いタスクを優先的に実行するタスクの限られたスケジュールである。キューの一つのタスクは、INSERTメソッドを呼び出すことです。
簡単なテストコード:
- package lhz.algorithm.chapter.six;
- /**
- * “ ”，《 》6.5
- * ：
- * A priority queue is a data structure for maintaining a set S of elements, each with an
- * associated value called a key. A max-priority queue supports the following operations.
- * • INSERT(S, x) inserts the element x into the set S. This operation could be written as S← S{x}.
- * • MAXIMUM(S) returns the element of S with the largest key.
- * • EXTRACT-MAX(S) removes and returns the element of S with the largest key.
- * • INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,
- * which is assumed to be at least as large as x's current key value.
- * ， 。 。
- * ： http://mushiqianmeng.blog.51cto.com/3970029/743611
- * @author lihzh( coder)
- */
- public class PriorityQueue {
-
- private final int DEFAULT_CAPACITY_VALUE = 16;
- // 16 （ )， 16 HashMap
- private int capacity = DEFAULT_CAPACITY_VALUE;
- private int[] quene = new int[capacity];
- //
- private int heapSize = 0;
-
- /**
- *
- * @return
- */
- public int maximum() {
- return quene[0];
- }
-
- /**
- * ，
- * INCREASE-Key ，
- * ：
- * MAX-HEAP-INSERT(A, key)
- * 1 heap-size[A] ← heap-size[A] + 1
- * 2 A[heap-size[A]] ← -∞
- * 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
- * ：O(lg n)
-
- * @param value
- */
- public void insert(int value) {
- // 1
- quene[heapSize] = value;
- heapSize++;
- increaceKey(heapSize, value);
- }
-
- /**
- * ， MaxHeap。
- *
- * ：
- * HEAP-INCREASE-KEY(A, i, key)
- * 1 if key < A[i]
- * 2 then error "new key is smaller than current key"
- * 3 A[i] ← key
- * 4 while i > 1 and A[PARENT(i)] < A[i]
- * 5 do exchange A[i] ↔ A[PARENT(i)]
- * 6 i ← PARENT(i)
- * ：O(lg n)
- * @param index
- * @param newValue
- */
- public void increaceKey (int heapIndex, int newValue) {
- if (newValue < quene[heapIndex-1]) {
- System.err.println(" ： ！");
- return;
- }
- quene[heapIndex-1] = newValue;
- int parentIndex = heapIndex / 2;
- while (parentIndex > 0 && quene[parentIndex-1] < newValue ) {
- int temp = quene[parentIndex-1];
- quene[parentIndex-1] = newValue;
- quene[heapIndex-1] = temp;
- heapIndex = parentIndex;
- parentIndex = parentIndex / 2;
- }
- }
-
- /**
- * （ ），
- * ：
- * HEAP-EXTRACT-MAX(A)
- * 1 if heap-size[A] < 1
- * 2 then error "heap underflow"
- * 3 max ← A[1]
- * 4 A[1] ← A[heap-size[A]]
- * 5 heap-size[A] ← heap-size[A] - 1
- * 6 MAX-HEAPIFY(A, 1)
- * 7 return max
- * ：O(lg n),
- * @return
- */
- public int extractMax() {
- if (heapSize < 1) {
- System.err.println(" !");
- return -1;
- }
- int max = quene[0];
- quene[0] = quene[heapSize-1];
- heapSize--;
- maxHeapify(quene, 1);
- return max;
- }
-
-
- /**
- *
- * @param array
- * @param index
- */
- private void maxHeapify(int[] array, int index) {
- int l = index * 2;
- int r = l + 1;
- int largest;
- // ， ，
- if (l <= heapSize && array[l-1] > array[index-1]) {
- largest = l;
- } else {
- largest = index;
- }
- // ， ，
- if (r <= heapSize && array[r-1] > array[largest-1]) {
- largest = r;
- }
- // ， 。
- if (largest != index) {
- int temp = array[index-1];
- array[index-1] = array[largest-1];
- array[largest-1] = temp;
- maxHeapify(array, largest);
- }
- }
- }
簡単なテストコード:
- public static void main(String[] args) {
- PriorityQueue q = new PriorityQueue();
- q.insert(2);
- q.insert(6);
- q.insert(3);
- q.insert(8);
- q.insert(7);
- q.insert(9);
- q.insert(1);
- q.insert(10);
- q.insert(9);
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- q.insert(9);
- q.insert(1);
- q.insert(10);
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- System.out.println(q.extractMax());
- }