什么是優(yōu)先隊(duì)列
一個(gè)普通隊(duì)列在刪除時(shí)郁稍，刪除最大或者最小的元素
方法定義
| 方法 | |
|---|---|
| MaxPQ() | 創(chuàng)建一個(gè)空隊(duì)列 |
| MaxPQ(Key[] a) | 創(chuàng)建一個(gè)具有初始化數(shù)據(jù)的隊(duì)列 |
| void insert(Key v) | 插入 |
| Key delMax() | 刪除最大元素磅废，并返回該元素 |
| boolean isEmpty() | 是否為空 |
| Key max() | 返回最大元素 |
| int size() | 返回隊(duì)列大小 |
二叉樹(后面將之成為堆)
節(jié)點(diǎn)為N的二叉樹纳像，高度為lgN
大(小)頂堆
每一個(gè)父節(jié)點(diǎn)都不小于它的子節(jié)點(diǎn)
數(shù)組實(shí)現(xiàn)二叉樹結(jié)構(gòu)
以索引1作為起始，1的位置存儲(chǔ)根結(jié)點(diǎn)拯勉，節(jié)點(diǎn)n的子節(jié)點(diǎn)為2n,2n+1竟趾，節(jié)點(diǎn)k的子節(jié)點(diǎn)為k/2
屏幕快照 2018-08-14 下午4.55.41.png
節(jié)點(diǎn)的提升
首先針對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行處理
循環(huán)比較，它與它的父節(jié)點(diǎn)宫峦，若大于父節(jié)點(diǎn)則進(jìn)行交換岔帽。
private void swim(int k)
{
while (k > 1 && less(k/2, k))
{
exch(k, k/2);
k = k/2;
}
}
節(jié)點(diǎn)的插入
public void insert(Key x)
{
pq[++N] = x;
swim(N);
}
節(jié)點(diǎn)的下降
若節(jié)點(diǎn)小于子節(jié)點(diǎn)，則將次節(jié)點(diǎn)循環(huán)下降
private void sink(int k)
{
while (2*k <= N)
{
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
刪除最大元素
將最頂部元素與末尾元素交換导绷，而后輸出末尾元素犀勒，并且將交換后的頂部元素再進(jìn)行sink
public Key delMax()
{
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}
算法復(fù)雜度分析
| 方法 | 復(fù)雜度 |
|---|---|
| insert | logN |
| delMax | logN |
堆排序
思路
- 構(gòu)造一個(gè)大頂堆，取堆頂元素妥曲，將堆頂元素與最后一個(gè)元素交換贾费。
- 將剩余元素重新構(gòu)成一個(gè)大頂堆
代碼實(shí)現(xiàn)
public class Heap
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N);
sink(a, 1, --N);
}
}
}
算法復(fù)雜度與特點(diǎn)分析
- 堆排序的算法復(fù)雜度為2NlogN,最壞為2NlogN，最好為NlogN
- 它是一個(gè)占用額外空間很小的算法
- 它是一個(gè)不穩(wěn)定算法
