堆的定义堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。 堆的特性
具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4, 5, 6和7，以此类推。
 如果一个结点的位置为k，则它的父结点的位置为 k/2，而它的两个子结点的位置则分别为 2k 和 2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从 a[k] 向上一层，就令 k 等于 k/2，向下一层就令k等于 2k 或 2k+1。
堆的设计
堆的实现插入方法insert的实现
堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱。 这个时候我们就需要通过一些方法（上浮算法）让刚才插入的这个数据放入到合适的位置。  所以，如果往堆中新插入元素，我们只需要不断的比较新结点 a[k] 和它的父结点 a[k/2] 的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。 删除最大元素delMax方法的实现
由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求。 这个时候我们就需要通过一些方法（下沉算法），让这个新的根结点放入到合适的位置。  所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点 a[k] 与它的子结点 a[2k] 和 a[2k+1] 中的较大者交换位置，即可完成堆的有序调整。 代码实现@SuppressWarnings('unchecked')public class Heap<E extends Comparable<E>> { /** * 用来存储元素的数组 */ private final E[] items; /** * 记录堆中元素的个数 */ private int n; /** * 创建容量为capacity的Heap对象 * * @param capacity 初始容量 */ public Heap(int capacity) { // 索引0 不放元素 this.items = (E[]) new Comparable[capacity + 1]; this.n = 0; } /** * 删除堆中最大的元素,并返回这个最大元素 */ public E delMax() { var max = items[1]; // 交换最大索引处的元素和max，让尾部的元素成为临时根节点 exch(1, n); // 删除最大索引处的元素 items[n] = null; // 元素个数 - 1 n--; // 通过下沉算法，让堆重新有序 sink(1); return max; } /** * 往堆中插入一个元素 */ public void insert(E e) { items[++n] = e; swim(n); } /** * 判断堆中索引i处的元素是否小于索引j处的元素 */ private boolean less(int i, int j) { return items[i].compareTo(items[j]) < 0; } /** * 交换堆中i索引和j索引处的值 */ private void exch(int i, int j) { var temp = items[j]; items[j] = items[i]; items[i] = temp; } /** * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置 */ private void swim(int k) { // 循环比较当前结点的值和其父节点的值，如果父节点比当前节点小，那么交换位置 while (k > 1) { // 比较父节点和当前节点的值 if (less(k / 2, k)) { exch(k / 2, k); } // 指针移动到父节点 k = k / 2; } } /** * 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 */ private void sink(int k) { // 比较当前节点和左右子节点的大小，与左右子节点中的较大值交换位置 while (2 * k <= n) { // 记录较大索引 int max; // 左右子节点的索引，按照堆的性质得知 var left = 2 * k; var right = 2 * k + 1; // 判断是否有右子节点 if (right <= n) { max = less(left, right) ? right : left; } else { max = left; } if (!less(k, max)) { break; } exch(k, max); k = max; } }}堆排序给定一个数组：String[] arr = {'S','O','R','T','E','X','A','M','P','L','E'}，请对数组中的字符按从小到大排序。 实现步骤
堆排序设计
堆构造过程堆的构造，最直观的想法就是另外再创建一个和新数组数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。 上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组 0~length-1 的数据拷贝到新数组的 1~length 处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可。  堆排序过程对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
 代码实现优先队列普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出队列中的最大值或者最小值。 例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。 普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就可以使用一种特殊的队列来完成这种需求，优先队列。  优先队列按照其作用不同，可以分为以下两种：
最大优先队列我们之前学习过堆，而堆这种结构是可以方便的删除最大的值，所以，接下来我们可以基于堆实现最大优先队列。 最大优先队列设计
最大优先队列代码实现@SuppressWarnings('unchecked')public class MaxPriorityQueue<E extends Comparable<E>> { private final E[] items; private int n; /** * 创建一个容量为capacity的最大优先队列 * * @param capacity 容量 */ public MaxPriorityQueue(int capacity) { this.items = (E[]) new Comparable[capacity + 1]; this.n = 0; } /** * 删除队列中最大的元素,并返回这个最大元素 * * @return 最大的元素 */ public E pop() { // 最大值就是堆顶元素 var max = items[1]; // 先交换堆顶元素和最大索引处的元素 swap(1, n); items[n--] = null; sink(1); return max; } /** * 添加一个元素 * * @param e 元素 */ public void add(E e) { items[++n] = e; // 使用上浮算法，把元素摆放到正确的位置 swim(n); } /** * 获取队列中元素的个数 * * @return 元素个数 */ public int size() { return n; } /** * 判断队列是否为空 * * @return 是否为空 */ public boolean isEmpty() { return n == 0; } /** * 判断堆中索引i处的元素是否小于索引j处的元素 */ private boolean less(int i, int j) { return items[i].compareTo(items[j]) < 0; } /** * 交换元素位置 */ private void swap(int i, int j) { var temp = items[i]; items[i] = items[j]; items[j] = temp; } /** * 上浮算法 * * @param k 索引位置 */ private void swim(int k) { // 索引1截止 while (k > 1) { // 父节点索引 var parent = k / 2; if (less(k, parent)) { // 如果父节点比当前节点大，那么应该可以退出循环了 break; } swap(k, parent); k = parent; } } /** * 下沉算法 * * @param k 索引位置 */ private void sink(int k) { while (2 * k <= n) { // 记录左右子节点较大者索引 int max; var left = 2 * k; var right = 2 * k + 1; // 这里是判断是否有右子节点 if (right <= n) { max = less(left, right) ? right : left; } else { max = left; } if (!less(k, max)) { // 如果左右子节点没有当前节点大，那么退出循环 break; } swap(k, max); k = max; } }}最小优先队列最小优先队列实现起来也比较简单，我们同样也可以基于堆来完成最小优先队列。 我们前面学习堆的时候，堆中存放数据元素的数组要满足都满足如下特性：
 其实我们之前实现的堆可以把它叫做最大堆，我们可以用相反的思想实现最小堆，让堆中存放数据元素的数组满足如下特性：
 这样我们就能快速的访问到堆中最小的数据。 最小优先队列设计
最小优先队列代码实现索引优先队列在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。 为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。 索引优先队列实现思路步骤一存储数据时，给每一个数据元素关联一个整数，例如insert(int k, E e)，我们可以看做k是t关联的整数，那么我们的实现需要通过k这个值，快速获取到队列中t这个元素，此时有个k这个值需要具有唯一性。 最直观的想法就是我们可以用一个E[] items数组来保存数据元素，在insert(int k, E e)完成插入时，可以把k看做是items数组的索引，把t元素放到items数组的索引k处，这样我们再根据k获取元素e时就很方便了，直接就可以拿到items[k]即可。  步骤二步骤一完成后的结果，虽然我们给每个元素关联了一个整数，并且可以使用这个整数快速的获取到该元素，但是，items数组中的元素顺序是随机的，并不是堆有序的。 所以，为了完成这个需求，我们可以增加一个数组 int[] pq，来保存每个元素在items数组中的索引，pq数组需要堆有序。 也就是说，pq[1] 对应的数据元素 items[pq[1]] 要小于等于 pq[2] 和 pq[3] 对应的数据元素 items[pq[2]] 和 items[pq[3]]。  步骤三通过步骤二的分析，我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是pq数组。 如果需要对 items 中的元素进行修改，比如让 items[0]='H'，那么很显然，我们需要对pq中的数据做堆调整，而且是调整 pq[9] 中元素的位置。 但现在就会遇到一个问题，我们修改的是 items 数组中0索引处的值，如何才能快速的知道需要挑中 pq[9] 中元素的位置呢？最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可，但是效率很低。 我们可以另外增加一个数组 int[] qp，用来存储pq的逆序。 例如：在pq数组中：pq[1]=6，那么在qp数组中，把6作为索引，1作为值，结果是：qp[6]=1。 当有了pq数组后，如果我们修改 items[0]='H'，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=9，那么直接调整 pq[9] 即可。 索引优先队列设计
索引优先队列代码实现@Slf4j@SuppressWarnings('unchecked')public class IndexMinPriorityQueue<E extends Comparable<E>> { /** * 用来存储元素的数组 */ private final E[] items; /** * 记录堆中元素的个数 */ private int n; /** * 保存每个元素在items数组中的索引，pq数组需要堆有序 */ private final int[] pq; /** * 保存qp的逆序，pq的值作为索引，pq的索引作为值 */ private final int[] qp; public IndexMinPriorityQueue(int capacity) { this.items = (E[]) new Comparable[capacity + 1]; this.n = 0; this.pq = new int[capacity + 1]; this.qp = new int[capacity + 1]; // 默认情况下，队列中没有存储任何元素，让qp中的元素都为-1 Arrays.fill(qp, -1); } /** * 往队列中插入一个元素,并关联索引i * * @param i 索引 * @param e 元素 */ public void add(int i, E e) { // 判断索引i处是否已经关联了元素，如果关联过了，不允许再插入 if (contains(i)) { throw new IllegalArgumentException('索引 ' + i + ' 已经被关联'); } // 元素个数 + 1，把i存储到pq中 pq[++n] = i; // 将元素存储到items对应的索引i items[i] = e; // 通过qp记录pq中的i qp[i] = n; // 上浮 swim(n); } /** * 删除队列中最小的元素,并返回该元素关联的索引 * * @return 该元素关联的索引 */ public E pop() { // 交换pq索引1和最大索引处的元素 exch(1, n); // 删除qp中对应的元素 var index = pq[n]; var minItem = items[index]; qp[index] = -1; // 删除pq最大索引处的元素 pq[n] = -1; // 删除items中对应的元素 items[index] = null; // 元素个数 - 1 n--; // pq下沉调整 sink(1); return minItem; } /** * 获取队列中元素的个数 */ public int size() { return this.n; } /** * 判断队列是否为空 */ public boolean isEmpty() { return this.n == 0; } /** * 判断k对应的元素是否存在 * * @param k 索引 * @return 是否存在 */ public boolean contains(int k) { return qp[k] != -1; } /** * 修改索引i处的元素 * * @param i 索引 * @param e 新的元素 */ public void changeItem(int i, E e) { items[i] = e; // pq中索引位置 var index = qp[i]; // 先上浮，后下沉 swim(index); sink(index); } /** * 最小元素关联的索引 */ public int minIndex() { // pq是堆有序的 return pq[1]; } /** * 删除索引i关联的元素 * * @param i 索引 */ public void delete(int i) { // pq中索引位置 var index = qp[i]; // 交换k和最大索引处的位置 exch(index, n); // 删除qp中对应的元素 var maxIndex = pq[n]; qp[maxIndex] = -1; // 删除pq最大索引处的元素 pq[n] = -1; // 删除items中对应的元素 items[index] = null; // 元素个数 - 1 n--; // 因为交换的位置是中间，所以需要先上浮，再下沉 swim(index); // pq下沉调整 sink(index); } /** * 判断堆中索引i处的元素是否小于索引j处的元素 * <p> * 注意，这里比较的实际上还是items里面元素的大小，而不是索引的大小 * * @param i 索引i * @param j 索引j */ private boolean less(int i, int j) { var indexI = pq[i]; var indexJ = pq[j]; return items[indexI].compareTo(items[indexJ]) < 0; } /** * 交换堆中i索引和j索引处的值 * * @param i 索引i * @param j 索引j */ private void exch(int i, int j) { // 交换pq中的数据 var temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; var indexI = pq[i]; var indexJ = pq[j]; // 更新pq中的数据 qp[indexI] = i; qp[indexJ] = j; // 这里为什么不动items？因为items并非堆有序，只有pq是堆有序 } /** * 上浮，是pq堆有序 */ private void swim(int k) { while (k > 1) { var parent = k / 2; // 如果k比父节点大，那么退出循环 if (!less(k, parent)) { break; } exch(k, parent); k = parent; } } /** * 下沉，是pq堆有序 */ private void sink(int k) { while (2 * k <= n) { int min; var left = 2 * k; var right = 2 * k + 1; if (right <= n) { // 取子节点中的较小者 min = less(left, right) ? left : right; } else { min = left; } // 如果k比子节点小，退出 if (less(k, min)) { break; } exch(k, min); k = min; } }} |
|
|
来自： 新用户15472188 > 《待分类》
