关于优先队列和hash的简介
一.优先队列的引入
JDK API中的定义如下:一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进 行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先 级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象;
1》add(),的方法:将指定的元素插入到队列中
这个方法的好处在于,它会自动增加队列的长度。
2》clear(),的方法:从此队列中移除所有元素
3》offer() :将指定的元素插入此优先级队列
4》peek()和poll()的区别;前者获取但不移除头元素,后者获取但会移除头元素。二者对于空队 列,都会返回一个null;
至于其它的方法,文档中有很清晰的介绍。
二.自己对于优先队列的看法
如果像文档那样实现各种方法,则需要写很多相关的类。其实我们可以通过一个简单的例题,来表 达其基本的操作。
例:给你很多的数,让你选出其中的10个最大的数。这里很多我们就以100进行量化、
以下是代码的具体实现:
public class MyListQueen {
int s[]=new int[10];
/**
*
* @param a 你要排序的数组
* @return 排好序的数组
*/
public void chushi(int a[]){
for(int i=0;i<a.length;i++){
for(int j=i+1;j<a.length;j++){
//进行交换
if(a[i]>a[j]){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
for(int k=0;k<10;k++)
s[k]=a[k];
}
/**
*
* 添加元素进行排序的
*/
public void addNode(int x,int i,int j){
if(j-i<=1){
for(int k=0;k<i;k++)
s[k]=s[k+1];
s[i]=x;
return;
}
int middle=(i+j)/2;
if(x<s[middle])
addNode(x,i,middle);
else if(x>s[middle])
addNode(x,middle,j);
}
/**
* 打印的方法
*/
public void Systemlist(){
for(int i=0;i<s.length;i++){
System.out.print(s[i]+",");
}
}
}
一个主类来运行
import java.util.Random;
public class TestList2 {
public static void main(String args[]){
MyListQueen list=new MyListQueen();
int a[]=new int[10];
Random random=new Random();
for(int i=0;i<10;i++){
a[i]=random.nextInt(100);
}
//初始数组
list.paixu(a);
//加入新的元素
for(int j=0;j<100;j++)
list.addNode(random.nextInt(100), 0, 10);//进行优先选择
list.Systemlist(); //打印数据
}
}
我是通过一个固定数组来保存需要的数据,当然你也可以通过固定结点的树来进行优先选择。
当然该问题实际上含有几个变量的。以上是选择最大的数,你也可以选择最小的数。选择的数的数 量也是一个变量。还有从多少数中选择等等。
三.hash结构的深度认识
有人会问,hash的结构是什么样?在我的脑海中,我可以形象的用一个数组加一个链表来描述。数组存放K值,链表并行的放那些具有相同K值的对象。
在这个结构中,时常会听见一些术语。
hash函数:其作用,相当于一个算法规则。给了相应的k值,你就可以通过hash函数求出对应的V值。它是该结构的逻辑支撑。也是产生该结构的 充要条件、(或许有更加精确的解释)
阀值:每个数组对应的链表长度(这是我的理解);
冲突:对于不同的关键字可能得到同一哈希地址,即Key1不等于Key2,而f(Key1)=f(Key2),这种现象称冲突、具有相同函数值的关键字对该哈希函数来说称做同义词。
哈希函数的构造方法:
1.直接定址法
取关键字或关键字的某个线性函数值为哈希地址。即:
H(key)=Key或H(key)=a*Key+b;
其中a和b为常数(这种哈希函数叫做自身函数).
2.数字分析法
取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。
等等构造方法,其实去网上我们都可以看到的。这里就不多说。一直想寻求hash表的应用,看了一些,感觉都是很抽象。要说就我所知道,hash表在查找上的应用较为突出。
构造一个hash表,通过hash函数,确定k值和存储地址的关系。通过这个关系,我们可以不通过比较就可以快速的查找出你需要的元素。
还有许多的方法,你可以通过百度了解。
分享到:
相关推荐
9.1 单端优先队列和双端优先队列 9.2 左倾树 9.3 二项式堆 9.4 Fibonacci堆 9.5 配偶堆 9.6 对称最小-最大堆 9.7 区间堆 9.8 参考文献和选读材料 第10章 高效二叉查找树 10.1 最优二叉查找树 10.2 AVL树 ...
(一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 三、树与二叉树 (一)树的概念 (二)二叉树 1.二叉树的定义及其主要特征 ...
数据结构:二叉树和一般树、优先队列:堆、左高树、竞赛树、搜索树、图 算法设计方法:贪心算法、分治算法、动态规划、回溯、分支限界等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一个坚实的基础。 ...
内容涵盖:第一章绪论、算法衡量指标、第二章线性表、顺序表、链表、第三章栈和队、栈、栈的应用举例、队列、循环队列、第四章串、串的模式匹配、第五章数组和广义表、稀疏矩阵的压缩存储方法:、广义表、第六章树和...
优先队列搜索,过最少的门救人,建图 A*搜索 图论 差分约束 Intervals bellman_ford Intervals SPFA 出纳员的雇佣 不等式组 图论 割边 图染色 拓扑 树 欧拉路径) 割点+统计删除后剩下多少连通图 删除一个点...
优先队列:堆结构的实现 经典题 括号匹配 表达式求值(中缀表达式转后缀表达式) 队列-层次遍历 栈实现队列、队列实现栈 双端队列-返回滑动窗口的最大值 小顶堆-返回数据流的第k大元素 leetcode建议练习题号: 业界...
数组(Array):连续存储元素的集合,可以通过索引访问元素。插入和删除元素的时间复杂度较高,为 O(n),但...哈希表(Hash Table):使用哈希函数将键映射到存储位置的数据结构,可以实现快速的插入、删除和查找操作。
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed ...哈希表(Hash ...哈希函数(Hash ...优先队列(Priority Queue) 堆
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed ...哈希表(Hash ...哈希函数(Hash ...优先队列(Priority Queue) 堆
优先队列(使用基于数组的二叉堆) 链表操作: 插 附加 返回索引 更新索引 删除索引 插入索引 插入索引后 删除数据 删除所有数据 在每个数据之后插入 在每个数据之前插入 删除列表 复制列表 findMthToLastNode 类型...
优先队列 交换节点对 中等的 从排序数组中删除重复项 简单的 删除元素 简单的 在旋转排序数组中搜索 中等的 二分搜索 查找排序数组中元素的第一个和最后一个位置 中等的 二分搜索 数独解算器 难的 回溯 组合和 中等...
队列、栈 hash(哈希) 数组、链表 82[M]. 138[M]. 142[M]. 143[M]. 148[M]. 328[M]. 430[M]. 817[M]. 跳表 字典树 208[M]. 211[M]. 位图(bitmap) 树 排序 179[M]. 查找 35[E]. 二分查找 852[E]. binary search 349[E]...
功能列表数据结构优先队列堆rbtree(red_black_tree) 地图/多地图集/多集位图布隆过滤器hamt(hash_array_mapped_trie) 克塔玛跳过列表算法排序(快速排序) 稳定排序(合并排序) binary_search 下界upper_bound ...
leetcode二维数组搜索力码 力扣解决方案。 在大多数情况下,始终尝试优化...或者,如果需要某种排序,则使用优先队列(堆)。 关于圆形数组,可能的解决方案是: -- 将数组与其副本连接以获得双倍长度的新数组。 但需
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
1.最短路(优先队列dijkstra) 2.判断环(tarjan算法) 3.最小生成树(Kruskal 模板) 4.最小生成树(Prim) 5.Dicnic最大流(最小割) 6.无向图最小环(floyd) 7.floyd算法的动态规划(通过部分指定边的最短路) 8.图中找出两点...
:优先队列 :并查集 剑指offer 链表 动态规划 动态规划思想: 动态规划的每个阶段可以从之前的某个阶段的“某个”或“某些”转态得到,得到的这样状态即为“状态转移” () 贪心算法 总是做出局部最优的选择,寄希望...
高级:栈stack,队列queue,双端队列deque,集合set,映射map(hash or map) 二维数据结构 基础:树tree,图graph 高级:二叉搜索树binary search tree(red-black tree,AVL),堆heap,并查集disjoint set,字典树...