数据结构培训教程(ppt 46页)

数据结构培训教程目录：
一、树和森林
二、二叉树
三、遍历
四、隔三遍历
五、完全二叉树
六、堆
七、问题
八、带HASH的堆
九、优先队列
十、哈夫曼树
十一、Huffman树
十二、排序算法
十三、快速排序
十四、其他排序法
十五、稳定性
十六、哈希表
十七、字符串的hash函数
……

 

数据结构培训教程内容提要：
带HASH的堆：
根据题中数据范围以及两两不等。
A[i]代表元素大小为i的元素在堆中的位置
这样修改的复杂度降为O(1)
修改后调整复杂度为O(log n)
总修改的复杂度为O(log n)
应用
SPFA
优先队列：
一般来说优先队列就是用堆
例子
dijkstra算法用优先队列优化O((n+m)logn)
动态维护中位数问题，一个集合，要支持插入操作和求当前中位数的操作，容易想到的是编程极其复杂的平衡树，但用优先队列会比较方便

..............................