优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就是如果他是大根堆那么父节点不小于子节点,如果是小根堆父节点不大于子节点。这也是一个递归定义。
为什么要是用优先队列?
插入的时候我们一般采用的方式就是上滤,也就是把要插入的元素放在最后面,然后比较让这个元素向上冒,知道正确的位置。
//插入
public void insert(int x) {
if (size > ele.length - 1) {
return;
}
//不使用0号元素
ele[++size] = x;
swim(size);
}
//上滤操作
private void swim(int index) {
while (index / 2 > 0) {
if (ele[index] > ele[index / 2]) {
int tep = ele[index];
ele[index] = ele[index / 2];
ele[index / 2] = tep;
}
index = index / 2;
}
}
在删除的时候我们再删除了最上面的元素之后我们还需要调整堆的平衡,这个时候我们采取的策略就是下滤,首先用最后一个元素代替要删除的那个元素,然后对该元素进行下滤,直到平衡。
//删除元素
public int deleteMax(){
int max = ele[1];
ele[1] = ele[size--];
sink(1);
return max;
}
//下滤
private void sink(int i) {
int index = i;
int tmp = ele[i];
while (i * 2 < size) {
int next = i * 2;
if (ele[next + 1] > ele[next]) {
++next;
}
if (ele[next] > tmp) {
// int temp = ele[index];
ele[index] = ele[next];
// ele[next] = temp;
index = next;
}
i = next;
}
ele[index] = tmp;
}
优先队列的很好的一个使用就是堆排序,他有比较好的性能,和优点。
堆排序分为两个步骤:
这样我们就建立了一个完整的优先队列了,接下来就是类似于删除最大元素最小元素的问题了。
这样我们就完成了整个的堆排序
public class HeapSort {
//下滤操作
public void sink(int[] arr,int i,int end) {
int index = i;
int tmp = arr[i];
while (i * 2 <= end) {
int n = i * 2;
if (n+1<=end&&arr[n] > arr[n + 1]) {
++n;
}
if (arr[n] < tmp) {
arr[index] = arr[n];
index = n;
}
i = n;
}
arr[index] = tmp;
}
public void sort(int[] arr) {
//构建堆
for (int i = arr.length / 2; i > 0; i--) {
sink(arr, i, arr.length - 1);
}
//从堆序生成顺序
int size = arr.length - 1;
while (size > 0) {
int tmp = arr[1];
arr[1] = arr[size];
arr[size] = tmp;
--size;
sink(arr, 1, size);
}
}
@Test
public void fun(){
int[] arr = new int[]{0, 7, 2, 5, 8, 3, 9};
sort(arr);
System.out.println(arr);
}
}
三大排序就是快排
,堆排序
,归并排序
。
看起来貌似堆排序是最完美的排序算法,但是其实不是的,下面就是一些缺点: