數據結構培訓教程(ppt 46頁)

數據結構培訓教程目錄：
一、樹和森林
二、二叉樹
三、遍曆
四、隔三遍曆
五、完全二叉樹
六、堆
七、問題
八、帶HASH的堆
九、優先隊列
十、哈夫曼樹
十一、Huffman樹
十二、排序算法
十三、快速排序
十四、其他排序法
十五、穩定性
十六、哈希表
十七、字符串的hash函數
……

數據結構培訓教程內容提要：
帶HASH的堆：
根據題中數據範圍以及兩兩不等。
A[i]代表元素大小為i的元素在堆中的位置
這樣修改的複雜度降為O(1)
修改後調整複雜度為O(log n)
總修改的複雜度為O(log n)
應用
SPFA
優先隊列：
一般來說優先隊列就是用堆
例子
dijkstra算法用優先隊列優化O((n+m)logn)
動態維護中位數問題，一個集合，要支持插入操作和求當前中位數的操作，容易想到的是編程極其複雜的平衡樹，但用優先隊列會比較方便

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