https://www.jianshu.com/p/94155f9616bf
引入
在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优先级有关......
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：
1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。
结构\操作 入队 出队
普通线性结构 O(1) O(n)
顺序线性结构 O(n) O(1)
普通线性结构实现的优先队列出队时间复杂度是O(n)，因为出队要拿出最优先的元素，也就是相对最大的元素（注意：大小是相对的，我们可以指定比较规则），从而要扫描一遍整个数组选出最大的取出才行。而对于顺序线性结构的入队操作，入队后可能破坏了原来的有序性，从而要调整当前顺序。
可以看到使用线性结构总有时间复杂度是O(n)的操作，还有没有更好的实现方式呢，当然是有的，这就要来聊一聊堆Heap。
堆
堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为最大堆和最小堆。
堆性质：
结构性：堆是一颗除底层外被完全填满的二叉树，底层的节点从左到右填入，这样的树叫做完全二叉树。即缺失结点的部分一定再树的右下侧。
堆序性：由于我们想很快找出最小元，则最小元应该在根上，任意节点都小于它的后裔，这就是小顶堆（Min-Heap）；如果是查找最大元，则最大元应该在根上，任意节点都要大于它的后裔，这就是大顶堆(Max-heap)。
堆的分类
最大堆：父亲节点的值大于孩子节点的值
最小堆：父亲节点的值小于孩子节点的值
数组表示堆
由于是完全二叉树，节点的索引之间有着一定的关系，故我们可以使用数组来存储二叉堆，具体如下：
如果从索引为0开始存储，则父亲和孩子节点的索引关系如下：
堆的实现
上浮操作(shift up)
当我们需要向一个最大堆添加一条新的数据时，此时我们的堆变成了这样。
此时，由于新数据的加入已经不符合最大堆的定义了。所以我们需要对新加入的数据进行shift up操作，将它放到它应该在的位置。shift up操作时我们将新加入的数据与它的父节点进行比较。如果比它的父节点大，则交换二者。
并且不断的重复这个操作，将它与父节点比较，直到它不大于父节点，或者它没有父节点（到顶了）。
此时我们就完成了 对新加入元素的shift up操作。
下沉操作(shift down)
当我们从堆中(也就是优先队列中)取出一个元素时。我们是将堆顶的元素弹出。(只能从堆顶取出)
此时这个堆没有顶了，那么该怎么办呢？我们只需要把这个堆最后一个元素放到堆顶就可以了。
此时这个堆已经不符合最大堆的性质。为了保持这个性质，我们需要将堆顶的元素调整到它应该在的位置。也就是对它进行shift Down操作。在shift down时，因为它有左右孩子两个节点，所以我们需要将左右两个孩子节点进行比较，在得到较大的节点之后，再与它进行比较，如果它的子节点大，则将二者交换。并且不断的重复这样的操作，直到它没有叶子节点或者大于叶子节点停止。
此时我们就完成了弹出一个元素之后的shift down操作。
堆排序
replace
replace:去除最大元素后，放入一个新元素
实现：可以先extractMax,再add，两次longn操作。
实现:将堆顶的元素替换以后sift down，一次O(logn)操作
heapify
将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),heapify的过程，算法的复杂度为O(n).
heapify:将任意数组整理成堆的形状。
首先将一个数组抽象成一个堆。这个过程，我们称之为heapify。
之后我们找到这个堆中第一个非叶子节点，这个节点的位置始终是数组的数量除以2，也就是索引5位置的27，从这个节点开始，对每一个非叶子的节点,，进行shift down操作。
27比它的子节点51要小，所以交换二者。
之后对索引4位置的11，以及索引3位置的25，继续进行shift down。
接下来我们看索引2位置的20。首先呢，我们需要将20与它两个子节点中较大的51交换。
此时，还没有完，shift down操作是直到它没有叶子节点或者大于叶子节点时才停止。
所以我们需要继续将20与它的子节点27进行比较。
索引2才算操作完成了。
最后继续对索引1位置的14，以此类推进行shiftdown。整个堆就操作完成。使用的时候每次取出堆顶的元素，整个数组就是排序完成的了。
heapfiy 的复杂度
每个节点堆化的时间复杂度是O(logn)，那个节点的堆化的总时间复杂度是O(nlogn)。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。
将每个非叶子节点的高度求和，得到下面的公式S1:
这个公式的求解稍微有点技巧，我们把公式左右都乘以2，得到另一个公式S2，再将S2减去S1，就可以得到S了。
S的中间部分是一个等比数列，用等比数列的求和公式来计算，最终的结果就是下图的样子。
因为
原地堆排序
所以 heapify() 时间复杂度是 O(n).
建堆后，数组中的数据是大顶堆。把堆顶元素，即最大元素，跟最后一个元素交换，那最大元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。
// n表示数据的个数，数组a中的数据从下标1到n的位置。
public class HeapSort {
public HeapSort() {
}
public static <E extends Comparable<E>> void sort(E[] data) {
MaxHeap<E> maxHeap = new MaxHeap();
for (E datum : data) {
maxHeap.add(datum);
}
for (int i = data.length - 1; i >= 0; i--) {
data[i] = maxHeap.extractMax();
}
}
//原地堆排序
public static <E extends Comparable<E>> void sort2(E[] data) {
if (data.length == 1) return;
//将数组整理成堆
//(data.length-2)/2:最后一个非叶子结点
//转换成堆
for (int i = (data.length - 2) / 2; i >= 0; i--) {
siftDown(data, i, data.length);
}
//进行堆排序
for (int i = data.length - 1; i >= 0; i--) {
swap(data, 0, i);
siftDown(data, 0, i);
}
}
//下沉操作
//对data[0,n)所形成的最大堆中，索引k的元素，执行siftdown
private static <E extends Comparable<E>> void siftDown(E[] data, int k, int n) {
//结点k的左孩子已经越界了,循环结束
while (2 * k + 1 < n) {
//左孩子的结点
int j = 2 * k + 1;
//右孩子的结点,判断有孩子是否存在，并且有孩子的值是否大于左孩子。
if (j + 1 < n && data[j + 1].compareTo(data[j]) > 0) {
j++;
}
//当前值比孩子的值小
if (data[k].compareTo(data[j]) > 0) {
break;
}
//交换
swap(data, k, j);
k = j;
}
}
private static <E extends Comparable<E>> void swap(E[] data, int i, int j) {
E ele = data[i];
data[i] = data[j];
data[j] = ele;
}
public static void main(String[] args) {
Integer[] arr = {1, 65, 98, 65, 5, 65, 12};
sort2(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
代码
package com.libin.setandmap;
import java.util.Random;
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap() {
this.data = new Array<>();
}
public int size() {
return data.getSize();
}
//返回一个布尔值，表示堆中是否为空
public boolean isEmpty() {
return data.isEmpty();
}
//返回完全二叉树数组表示中,一个索引表示的元素的父亲结点的索引。
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index-0 doesn't dont have parent");
}
return (index - 1) / 2;
}
//返回完全二叉树数组表示中,一个索引表示的元素的左孩子结点的索引。
private int leftChild(int index) {
return index * 2 + 1;
}
//返回完全二叉树数组表示中,一个索引表示的元素的右孩子结点的索引。
private int rightChild(int index) {
return index * 2 + 2;
}
public void add(E e) {
data.addLast(e);
//上浮的元素
siftUp(data.getSize() - 1);
}
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
//与父节点进行交换
data.swap(k, parent(k));
k = parent(k);
}
}
public E findMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("empty");
}
return data.get(0);
}
public E extractMax() {
E max = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return max;
}
//下沉操作
private void siftDown(int k) {
//结点k的左孩子已经越界了,循环结束
while (leftChild(k) < data.getSize()) {
//左孩子的结点
int j = leftChild(k);
//右孩子的结点,判断有孩子是否存在，并且有孩子的值是否大于左孩子。
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
//当前值比孩子的值小
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
//交换
data.swap(k, j);
k = j;
}
}
//去除最大元素,然后添加一个元素。
public E replace(E e) {
E ret = findMax();
data.set(0, e);
siftDown(0);
return ret;
}
//heapfiy
public MaxHeap(E[] arr) {
data = new Array<>(arr);
//去除最后一个元素的父元素。
for (int i = parent(arr.length - 1); i >= 0; i--) {
siftDown(i);
}
}
public static void main(String[] args) {
int n = 100;
Integer[] arr = new Integer[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] =random.nextInt(Integer.MAX_VALUE);
}
MaxHeap<Integer> maxHeap = new MaxHeap<>(arr);
for (int i = 0; i < n; i++) {
System.out.println(maxHeap.extractMax());
}
System.out.println("finisehd");
}
}
package com.libin.setandmap;
import java.util.Arrays;
public class Array<E> {
private E[] data;
private int size;
//构造函数，传入数组的容量capacity的Array
@SuppressWarnings("unchecked")
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
//午参构造函数，默认capacity为10
public Array(){
this(10);
}
public Array(E[] arr){
data = (E[]) new Object[arr.length];
for (int i = 0; i <arr.length ; i++) {
data[i] = arr[i];
}
size = arr.length;
}
//获取数组中元素个数
public int getSize(){
return size;
}
//获取数组的容量
public int getCapacity(){
return data.length;
}
//判断数组是否为空
public boolean isEmpty(){
return size == 0;
}
//在数组下标为index的位置插入一个元素
public void add(int index , E e){
if(index<0||index>size){
throw new IllegalArgumentException("add failed , required index > 0 and index < size");
}
if(size == data.length){
resize(data.length * 2);
}
for(int i=size-1;i>index;i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
//向所有元素后添加一个新元素
public void addLast(E e){
add(size , e);
}
//向所有元素前添加一个新元素
public void addFirst(E e){
add(0 , e);
}
//获取index索引位置的元素
public E get(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("get failed , required index > 0 and index < size");
}
return data[index];
}
//修改索引index位置的元素为e
public void set(int index, E e){
if(index<0||index>=size){
throw new IllegalArgumentException("set failed , required index > 0 and index < size");
}
data[index] = e;
}
//判断数组中是否含有元素e
public boolean contains(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return true;
}
}
return false;
}
//查找数组中是否含有元素e，返回相应元素的下标
public int find(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return i;
}
}
return -1;
}
//从数组中删掉相应下标的元素，返回删掉的元素
public E remove(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("remove failed , required index > 0 and index < size");
}
E ret = data[index];
for(int i=index+1;i<size;i++){
data[i-1] = data[i];
}
size--;
data[size] = null;
if(size == data.length/4 && data.length/2 != 0){
resize(data.length/2);
}
return ret;
}
//从数组中删掉第一个元素，返回删掉的元素
public E removeFirst(){
return remove(0);
}
//从数组中删掉最后一个元素，返回删掉的元素
public E removeLast(){
return remove(size-1);
}
//从数组中删掉元素e
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
public void swap(int i,int j){
E t = data[i];
data[i] = data[j];
data[j] =t;
}
@Override
public String toString() {
return "Array [data=" + Arrays.toString(data) + ", size=" + size +" Capacity="+data.length+ "]";
}
//重新设置数组容量
private void resize(int newCapacity){
@SuppressWarnings("unchecked")
E[] newData = (E[]) new Object[newCapacity];
for(int i=0;i<size; i++){
newData[i] = data[i];
}
data = newData;
}
}
优先队列
package com.libin.setandmap.heap;
public class PriorityQueue<E extends Comparable<E>>{
private MaxHeap<E> maxHeap;
public PriorityQueue() {
this.maxHeap = new MaxHeap();
}
public int getSize(){
return maxHeap.size();
}
public boolean isEmpty(){
return maxHeap.isEmpty();
}
public E getFront(){
return maxHeap.findMax();
}
public void enqueue(E e){
maxHeap.add(e);
}
public E deQueue(){
return maxHeap.extractMax();
}
}
快排思想和优先队列比较
topk和selectk问题既可以使用快排思想解决，也可以使用优先队列解决。
快排:O(n) 空间O(1)
优先队列:O(nlogk) 空间O(k)
优先队列的有i是，不需要一次性知道所有数据,数据流的方式处理。
