1: 优先队列
不是先进先出,是按照冒个规则,出:
2: 堆排序
1: 建堆
2: 堆顶与最后一个节点调换,堆顶出堆,重新调整堆
小顶堆: 节点i< 2i(左孩子) && i< 2i+1 (右孩子)
建立堆:(递归)当前i节点 和i/2 比较 如果i小于i/2 交换
调整堆: 顶点开始 ,(去左右节点中最小的)比较 ,若 孩子节点小 继续递归
若 孩子节点大 退出 (因为本身已经是堆排序的)
package com.algorithm.common; import java.util.Iterator; import java.util.NoSuchElementException; /** * 堆排序的最小优先队列 * @author lijunqing */ public class MinPQ<Key> implements Iterable<Key> { private Key[] pq; private int N; public MinPQ() { this(1); N=0; } public MinPQ(int initCapacity) { pq=(Key[])new Object[initCapacity + 1]; N=0; } /** * 插入一个节点 * @param key */ public void insert(Key key) { if(N == pq.length - 1) { resize(2 * pq.length); } N++; pq[N]=key; swim(N); } /** * 堆顶和最后一个节点交互 堆顶出堆 从堆顶开始调整堆 * @return */ public Key delMin() { exch(1, N); Key min=pq[N]; pq[N]=null; N--; skin(1); // 调整堆 return min; } /** * 从i节点开始调整堆 * @param i */ private void skin(int i) { while(2 * i <= N) { int k=2 * i; if(k < N && greater(k, k + 1)) { // 比较右节点小 取右节点 k++; } if(greater(k, i)) { // 如果孩子节点大 不需要调整了 break; } exch(i, k); i=k; } } /** * 递归交互子父节点 * @param i */ private void swim(int i) { while(i > 1 && greater(i / 2, i)) { exch(i, i / 2); i=i / 2; } } /** * 交互节点值 * @param i * @param j */ private void exch(int i, int j) { Key temp=pq[i]; pq[i]=pq[j]; pq[j]=temp; } /** * 子节点小于父节点 [key是带有compare的] 只能现在用的数字 * @param i * @param i2 * @return */ private boolean greater(int i, int j) { return ((Comparable<Key>)pq[i]).compareTo(pq[j]) > 0; } /** * 重新申请空间 * @param capacity */ private void resize(int capacity) { Key[] temp=(Key[])new Object[capacity]; for(int i=0; i < pq.length; i++) { temp[i]=pq[i]; } pq=temp; } public int size() { return N; } public boolean isEmpty() { if(N == 0) { return true; } return false; } @Override public Iterator<Key> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Key> { // 重新建一个 private MinPQ<Key> copy; public HeapIterator() { copy=new MinPQ<Key>(size()); 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(); } } public static void main(String[] agrs) { MinPQ<Integer> minPQ=new MinPQ<Integer>(); minPQ.insert(25); minPQ.insert(6); minPQ.insert(9); minPQ.insert(10); minPQ.insert(3); minPQ.insert(23); Iterator<Integer> m=minPQ.iterator(); while(m.hasNext()) { System.out.println(m.next()); } } }
结果:
3
6
9
10
23
25
相关推荐
这些特性使得堆成为实现优先队列的理想选择。 **大根堆与小根堆** 大根堆和小根堆是堆的两种基本类型。大根堆中,根节点总是集合中最大(或最小)的元素,确保了在任何时候,堆顶的元素都是最大的。相反,小根堆的...
数组实现优先队列的核心思想是维护一个最小堆(最小堆是堆数据结构的一种,每个父节点的值都小于或等于其子节点的值)。插入元素时,将元素放在数组的末尾,然后通过上浮操作调整堆以保持最小堆性质。删除队首元素...
2. 优先队列:堆可以用来实现优先队列,例如 Job Scheduling、Resource Allocation等。 3. 图算法:堆可以用来解决图论问题,例如最短路径、最小生成树等。 堆和堆排序是一种重要的数据结构和算法,广泛应用于...
堆排序是一种基于比较的排序算法...`Heap.java`文件可能是实现堆排序或优先队列的一个Java源代码文件,可能包含了上述讨论的堆构造、插入、删除等相关方法。你可以通过阅读和理解这个文件来深入学习堆排序的实现细节。
优先队列在Java编程中是一种特殊的数据结构,它遵循特定的出队顺序,通常是最小元素(最小优先队列)或最大元素(最大优先队列)先出队。这种数据结构在解决各种问题时非常有用,例如任务调度、事件驱动编程、搜索...
优先队列排序的效率与堆排序相当,其操作如插入、删除最小元素(或最大元素)的时间复杂度为O(log n)。优先队列排序适用于需要频繁查找最大或最小元素,且需动态插入和删除元素的场景。 在C/C++环境中,VC++编译器...
1. 堆排序:使用优先队列实现堆排序算法。 2. 哈夫曼编码:使用优先队列实现哈夫曼编码算法。 四、图的定义和实现 1. 图的定义:图是用线或边连接在一起的顶点或节点的集合,记为 G = (V,E),其中 V 是顶点集,E ...
二叉堆的性质使得其在实现优先队列时非常高效,特别是插入(Insert)和删除最大(或最小)元素(RemoveMax 或 RemoveMin)操作的时间复杂度可以保持在对数时间内,即O(log n)。 在课程中提到的具体问题解决实例包括...
总的来说,这个项目通过小大根交替堆实现的双端优先队列,结合学生信息,可以高效地处理学生成绩的查询、排序和管理,尤其是在需要快速获取最高分和最低分的情况下。这种数据结构的设计和实现对于学习数据结构和算法...
对整个优先队列执行堆排序,首先从最后一个非叶子节点开始自底向上调整,构建小顶堆,然后将堆顶元素与末尾元素交换,删除堆顶元素,重复这个过程,直至整个队列有序。 7. `SSearchElem`和`SSearchWeigth`函数: ...
优先队列作为堆排序的一个经典应用场景,常用于需要高效处理数据的场合,如操作系统中的进程调度、事件驱动系统中处理高优先级任务等。此外,堆排序在解决Top-K问题中也发挥着重要作用,即在大数据集中快速找到前K个...
- Java的`java.util.PriorityQueue`是优先队列的实现,它基于二叉堆(通常是最小堆),满足堆的性质:父节点的优先级总是不小于子节点。 - PriorityQueue支持`add()`、`offer()`、`peek()`、`poll()`等方法,分别...
堆是一种完全二叉树,满足堆性质:父节点的键值总是大于或等于(最小优先队列)或小于或等于(最大优先队列)其子节点的键值。这样可以确保根节点始终是最小或最大元素,从而方便快速地执行Extract-Min或Extract-Max...
1. **数组实现**:基础的数据结构可以是一个动态调整大小的数组,使用堆排序的思想来维护优先级。最小堆或最大堆是最常见的选择,前者保证队列顶部总是最小值,后者则是最大值。 2. **链表实现**:另一种方法是使用...
3. **堆排序**:使用优先队列进行快速排序。 4. **最短路径问题**:解决单源最短路径问题,如Prim算法和Kruskal算法。 在实际项目中,通过理解和熟练掌握优先队列数据类型,我们可以解决很多复杂的问题,提高算法...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,每个父节点的值都大于或等于其子节点的值;在小顶堆中,父节点的值小于或等于子节点的值。这种数据结构类似于一个完全二叉树...
3. **堆排序:** 堆排序算法利用优先队列(通常是最大堆),通过反复从堆中取出最大元素并将其放到序列的末尾,实现对序列的升序排序。 4. **事件模拟:** 在模拟事件驱动的系统时,优先队列用于管理事件的触发顺序...
在本文中,我们将深入探讨基于VC的堆和最大优先队列的实现,这些实现是通过C++编程语言完成的。堆是一种特殊的树形数据结构,它满足特定的性质,如最大堆或最小堆,常被用于优化算法和解决各种问题。在VC(Visual ...
这种数据结构常用于优先队列的实现,因为它可以快速找到最大或最小元素。 1. 堆排序:堆排序是一种高效的排序算法,基于比较排序,其时间复杂度为O(n log n)。基本步骤包括构建初始堆、交换堆顶元素(最大元素)与...
堆可以看作是一个近似最大或最小元素的优先队列。在C++中,可以使用标准库中的`std::make_heap`、`std::push_heap`、`std::pop_heap`和`std::sort_heap`等函数来实现堆排序。 **归并排序(Merge Sort)** 归并排序...