堆数据结构总结
一、最小堆(最大堆)
package com.ldl.algorithms.Exercise; /************************************************************************* * Compilation: javac MinPQ.java * Execution: java MinPQ < input.txt * * Generic min priority queue implementation with a binary heap. * Can be used with a comparator instead of the natural order. * * % java MinPQ < tinyPQ.txt * E A E (6 left on pq) * * We use a one-based array to simplify parent and child calculations. * *************************************************************************/ import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; import com.ldl.algorithms.StdIn; import com.ldl.algorithms.StdOut; /** * The <tt>MinPQ</tt> class represents a priority queue of generic keys. * It supports the usual <em>insert</em> and <em>delete-the-minimum</em> * operations, along with methods for peeking at the maximum key, * testing if the priority queue is empty, and iterating through * the keys. * <p> * The <em>insert</em> and <em>delete-the-minimum</em> operations take * logarithmic amortized time. * The <em>min</em>, <em>size</em>, and <em>is-empty</em> operations take constant time. * Construction takes time proportional to the specified capacity or the number of * items used to initialize the data structure. * <p> * This implementation uses a binary heap. * <p> * For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. */ public class MinPQ<Key> implements Iterable<Key> { private Key[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator<Key> comparator; // optional comparator /** * Create an empty priority queue with the given initial capacity. */ public MinPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Create an empty priority queue. */ public MinPQ() { this(1); } /** * Create an empty priority queue with the given initial capacity, * using the given comparator. */ public MinPQ(int initCapacity, Comparator<Key> comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Create an empty priority queue using the given comparator. */ public MinPQ(Comparator<Key> comparator) { this(1, comparator); } /** * Create a priority queue with the given items. * Takes time proportional to the number of items using sink-based heap construction. */ public MinPQ(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 isMinHeap(); } /** * Is the priority queue empty? */ public boolean isEmpty() { return N == 0; } /** * Return the number of items on the priority queue. */ public int size() { return N; } /** * Return the smallest key on the priority queue. * Throw an exception if no such key exists because the priority queue is empty. */ public Key min() { if (isEmpty()) throw new RuntimeException("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; } /** * Add a new key to the priority queue. */ 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 isMinHeap(); } /** * Delete and return the smallest key on the priority queue. * Throw an exception if no such key exists because the priority queue is empty. */ public Key delMin() { if (N == 0) throw new RuntimeException("Priority queue underflow"); exch(1, N); Key min = pq[N--]; sink(1); pq[N+1] = null; // avoid loitering and help with garbage collection if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMinHeap(); return min; } /*********************************************************************** * Helper functions to restore the heap invariant. **********************************************************************/ 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; } } /*********************************************************************** * Helper functions for compares and swaps. **********************************************************************/ private boolean greater(int i, int j) { if (comparator == null) { return ((Comparable<Key>) 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 min heap? private boolean isMinHeap() { return isMinHeap(1); } // is subtree of pq[1..N] rooted at k a min heap? private boolean isMinHeap(int k) { if (k > N) return true; int left = 2*k, right = 2*k + 1; if (left <= N && greater(k, left)) return false; if (right <= N && greater(k, right)) return false; return isMinHeap(left) && isMinHeap(right); } /*********************************************************************** * Iterators **********************************************************************/ /** * Return an iterator that iterates over all of the keys on the priority queue * in ascending order. * <p> * The iterator doesn't implement <tt>remove()</tt> since it's optional. */ public Iterator<Key> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Key> { // create a new pq private MinPQ<Key> 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 MinPQ<Key>(size()); else copy = new MinPQ<Key>(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.delMin(); } } /** * A test client. */ public static void main(String[] args) { MinPQ<String> pq = new MinPQ<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMin() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } }
二、索引最小堆(索引最大堆)
package com.ldl.algorithms.Exercise; /************************************************************************* * Compilation: javac IndexMinPQ.java * Execution: java IndexMinPQ * * Indexed PQ implementation using a binary heap. * *********************************************************************/ import java.util.Iterator; import java.util.NoSuchElementException; import com.ldl.algorithms.StdOut; public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> { 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 NMAX) { keys = (Key[]) new Comparable[NMAX + 1]; // make this of length NMAX?? pq = new int[NMAX + 1]; qp = new int[NMAX + 1]; // make this of length NMAX?? for (int i = 0; i <= NMAX; i++) qp[i] = -1; } // is the priority queue empty? public boolean isEmpty() { return N == 0; } // is k an index on the priority queue? public boolean contains(int k) { return qp[k] != -1; } // number of keys in the priority queue public int size() { return N; } // associate key with index k public void insert(int k, Key key) { if (contains(k)) throw new NoSuchElementException("item is already in pq"); N++; qp[k] = N; pq[N] = k; keys[k] = key; swim(N); } // return the index associated with a minimal key public int minIndex() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // return a minimal key public Key minKey() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return keys[pq[1]]; } // delete a minimal key and returns its associated index 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[pq[N+1]] = null; // to help with garbage collection pq[N+1] = -1; // not needed return min; } // return key associated with index k public Key keyOf(int k) { if (!contains(k)) throw new NoSuchElementException("item is not in pq"); else return keys[k]; } // change the key associated with index k public void change(int k, Key key) { changeKey(k, key); } // change the key associated with index k public void changeKey(int k, Key key) { if (!contains(k)) throw new NoSuchElementException("item is not in pq"); keys[k] = key; swim(qp[k]); sink(qp[k]); } // decrease the key associated with index k public void decreaseKey(int k, Key key) { if (!contains(k)) throw new NoSuchElementException("item is not in pq"); if (keys[k].compareTo(key) <= 0) throw new RuntimeException("illegal decrease"); keys[k] = key; swim(qp[k]); } // increase the key associated with index k public void increaseKey(int k, Key key) { if (!contains(k)) throw new NoSuchElementException("item is not in pq"); if (keys[k].compareTo(key) >= 0) throw new RuntimeException("illegal decrease"); keys[k] = key; sink(qp[k]); } // delete the key associated with index k public void delete(int k) { if (!contains(k)) throw new NoSuchElementException("item is not in pq"); int index = qp[k]; exch(index, N--); swim(index); sink(index); keys[k] = null; qp[k] = -1; } /************************************************************** * General helper functions **************************************************************/ 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; } /************************************************************** * Heap helper functions **************************************************************/ 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; } } /*********************************************************************** * Iterators **********************************************************************/ /** * Return an iterator that iterates over all of the elements on the * priority queue in ascending order. * <p> * The iterator doesn't implement <tt>remove()</tt> since it's optional. */ public Iterator<Integer> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Integer> { // create a new pq private IndexMinPQ<Key> 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<Key>(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(); } } public static void main(String[] args) { // insert a bunch of strings String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" }; IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length); for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // delete and print each key while (!pq.isEmpty()) { int i = pq.delMin(); StdOut.println(i + " " + strings[i]); } StdOut.println(); // reinsert the same strings for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // print each key using the iterator for (int i : pq) { StdOut.println(i + " " + strings[i]); } while (!pq.isEmpty()) { pq.delMin(); } } }
三、堆排序
public class Heap { public static void sort(Comparable[] pq) { int N = pq.length; for (int k = N/2; k >= 1; k--) sink(pq, k, N); while (N > 1) { exch(pq, 1, N--); sink(pq, 1, N); } } /*********************************************************************** * Helper functions to restore the heap invariant. **********************************************************************/ private static void sink(Comparable[] pq, int k, int N) { while (2*k <= N) { int j = 2*k; if (j < N && less(pq, j, j+1)) j++; if (!less(pq, k, j)) break; exch(pq, k, j); k = j; } } /*********************************************************************** * Helper functions for comparisons and swaps. * Indices are "off-by-one" to support 1-based indexing. **********************************************************************/ private static boolean less(Comparable[] pq, int i, int j) { return pq[i-1].compareTo(pq[j-1]) < 0; } private static void exch(Object[] pq, int i, int j) { Object swap = pq[i-1]; pq[i-1] = pq[j-1]; pq[j-1] = swap; } // is v < w ? private static boolean less(Comparable v, Comparable w) { return (v.compareTo(w) < 0); } /*********************************************************************** * Check if array is sorted - useful for debugging ***********************************************************************/ private static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } // Read strings from standard input, sort them, and print. public static void main(String[] args) { String[] a = StdIn.readStrings(); Heap.sort(a); show(a); } }
四、最小最大堆(最大最小堆),即双端堆。见前面的博文。
五、用最小堆和最大堆实现中位数查找。见前面博文。
六、查找最大的M个元素
这里要用最小堆来实现。为什么呢? 我们首先要创建一个容量为M的最小堆,当这个最小堆满时,容纳的是当前最大的M个元素,但是它们是以最小堆次序排列的,也就是堆顶为当面M个元素中的最小元素。当下一个新元素来到时,为了保证当前堆中的M个元素始终未当前最大的M个元素,我们应该要淘汰(删除)堆中的最小的那个元素,也就是最小堆的堆顶元素。所以,为了方便更新维护对,我们必须采用最小堆。
package com.ldl.algorithms.Exercise; /************************************************************************* * Compilation: javac TopM.java * Execution: java TopM M < input.txt * Dependencies: MinPQ.java Transaction.java StdIn.java StdOut.java * Data files: http://algs4.cs.princeton.edu/24pq/tinyBatch.txt * * Given an integer M from the command line and an input stream where * each line contains a String and a long value, this MinPQ client * prints the M lines whose numbers are the highest. * * % java TopM 5 < tinyBatch.txt * Thompson 2/27/2000 4747.08 * vonNeumann 2/12/1994 4732.35 * vonNeumann 1/11/1999 4409.74 * Hoare 8/18/1992 4381.21 * vonNeumann 3/26/2002 4121.85 * *************************************************************************/ import com.ldl.algorithms.StdIn; import com.ldl.algorithms.StdOut; public class TopM { // Print the top M lines in the input stream. public static void main(String[] args) { int M = Integer.parseInt(args[0]); MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1); while (StdIn.hasNextLine()) { // Create an entry from the next line and put on the PQ. String line = StdIn.readLine(); Transaction transaction = new Transaction(line); pq.insert(transaction); // remove minimum if M+1 entries on the PQ if (pq.size() > M) pq.delMin(); } // top M entries are on the PQ // print entries on PQ in reverse order Stack<Transaction> stack = new Stack<Transaction>(); for (Transaction transaction : pq) stack.push(transaction); for (Transaction transaction : stack) StdOut.println(transaction); } }
相关推荐
、第七章图、图的存储结构:、图的遍历、深度优先遍历(DFS)、广度优先遍历(BFS算法)、最小生成树、普里姆算法、克鲁斯卡尔算法、最短路径、迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法、拓扑排序、关键路径、第八...
一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
摊还分析11.1 一个无关的智力问题11.2 二项队列11.3 斜堆11.4 斐波那契堆11.4.1 切除左式堆中的节点11.4.2 二项队列的懒惰合并11.4.3 斐波那契堆操作11.4.4 时间界的证明11.5 伸展树总结练习参考文献第12章 高级数据...
一共五页,包括数据结构总结,图的总结,以及(1)直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序(5)简单选择排序(6)堆排序(7)归并排序(8)基数排序的例子。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
将数据结构中的排序算法,如选择排序,冒泡排序,插入排序,希尔排序,快速排序,堆排序等排序算法做出总结,IT程序员笔试面试必备。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
小码哥恋上数据结构课程课件pdf格式 01-学前须知.pdf 02-开发环境,pdf 03-复杂度.pdf 04-动态数组.pdf 05-链表.pdf 06-栈.pdf 07-队列.pdf 08-二叉树.pdf 09-二又搜索树.pdf 10-平衡二又搜索树.pdf 11-AVL树.pdf 12...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
同时,我们还将运用栈、队列、堆等基本数据结构,实现更加复杂的操作。除了对数据结构的基本操作进行实现之外,我们还需要考虑时间和空间复杂度等重要问题,以确保算法的执行效率和程序的稳定性。最后,在实验报告中...
数据结构中排序总结:冒泡、交换、选择、插入、基数、Shell、快速、归并、堆
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
同时,我们还将运用栈、队列、堆等基本数据结构,实现更加复杂的操作。 除了对数据结构的基本操作进行实现之外,我们还需要考虑时间和空间复杂度等重要问题,以确保算法的执行效率和程序的稳定性。 最后,在实验报告...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...
道01数据结构和算法绪论. mp402_谈谈算法. mp4 西03_时间复杂度和空间复杂度.mp404_时间复杂度和空间复杂度2.mp405_时间复杂度和空间复杂度3.mp4险06线性表. mp407_线性表2. mp408_线性表3. mp4品09_ 线性表4. mp...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...