优先级队列的介绍：

1.1优先级队列：优先级队列是一种特殊的队列数据结构，每个元素都有一个与之关联的优先级，与普通队列不同，优先级队列中的元素是按照优先级顺序进行处理的，而不是简单的插入。

特点：

1.优先级：每个元素都有一个优先级。优先级可以是数值或是其他标识，通常较高的数值表示更高的优先级

2.出队顺序：在优先级队列中，优先级高的元素会被先处理。

堆的介绍：

2.1堆的定义： 堆是一种特殊的树形结构（完全二叉树），主要用于实现优先队列。堆有两种类型：最大堆和最小堆。

堆的性质：

最大堆：每个节点的值大于或等于其子节点的值。 根节点是最大值。

最小堆：每个节点的值小于或等于其子节点的值。根节点是最小值。

2.2： 堆的存储方式：

由于堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来进行高效存储。

对于非完全二叉树不适合顺序存储，因为为了还原二叉树，需要储存空节点，导致空间利用率下降。

2.3 堆的创建：

如何将上述二叉树创建成堆？

由上图我们可以直到了解，除了根节点外，该完全二叉树左右子树均满足堆的性质(最小堆满足)，因此我们只需将根节点向下调整即可。

2.3.1 堆的向下调整（也叫下沉）：

1.parent标记需要调整的节点，child标记parent的左孩子（parent如果有孩子，一定是先有左孩子）

2.如果parent的左孩子存在，即child< size,进行以下操作直至parent的左孩子不存在：

    （1): parent的右孩子是否存在，存在，找到左右孩子中最小的那个，让child进行标记。

   （2):  将parent与较小的那个孩子进行比较，如果：

        parent 小于较小的那个孩子child,调整结束。

否则：交换parent 与 较小的孩子child ，交换完成之后，parent中大的那个元素向下移动，可能会导致子树不满足堆的性质，因此需要继续向下调整，即parent = child,child = 2*parent+1;

具体代码如下:

   public void shiftDown(int parent,int UsedSize){int child = 2*parent+1;while(child<usedSize){//找到左右孩子的最大值if(child+1< usedSize && elem[child] < elem[child+1]){child++;}if(array[parent]<= array[child]){break; //满足最小堆的特性}else{//将双亲与最小孩子进行交换位置int t = array[parent];array[parent] = array[child];array[child] = t;//parent的较大元素向下移动可能会导致子树不满足堆的性质，因此还需向下调整parent = child;child = 2*parent+1;}}}

注：在调整以parent为根的二叉树时，必须满足parent的左右子树都已经是根了才能向下调整。

时间复杂度的分析：

最坏的情况即为图示情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(log2n).

2.3.2 : 堆的创建

对于普通节点，根的左右子树不满足堆的性质，该如何调整？

找到倒数第一个非叶子节点，从该位置往前一直到根节点，遇到一个节点，进行向下调整。

    public void CreatHeap(){int root = (this.usedSize-1-1)/2;for(;root>=0;root--){shiftDown(root,usedSize);}}

2.4  堆的插入和删除：

2.4.1：堆的插入：

思路：

1.将元素放到底层空间中（空间不够时需要扩容）。

2.将最后插入的节点向上调整，直到满足了堆的性质。

向上调整堆：

将插入后的节点向上调整直到满足堆性质。

具体代码如下：（以最小堆为例）

public void offer(int val){if(isFull()){ //堆满了，进行扩容elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val; //将val插到数组最后一个位置 shiftUp(usedSize);usedSize++; //有效元素个数加1}//向上调整（上移）最小堆：public void shiftUp(int child){//找到child的双亲：int parent = (child-1)/2;while(child>0){//如果双亲比孩子都小,满足最小堆if(array[parent]< array[child]){break;}else{//将双亲与孩子节点进行交换int t = array[parent];array[parent] = array[child];array[child] = t;//小的元素继续向上移动，可能子树不满足堆的性质，继续上移parent = child;child = (child-1)/2;}}}}

2.4.2 堆的删除：

思路：

1.堆的删除删除的一定是堆顶元素。

2.将堆中的有效数据个数-1

3.对堆顶元素进行向下调整

具体代码如下：

   private void swap(int[] elem,int i,int j){int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}public int poll(){if(isEmpty()){return -1;}int val = elem[0]; //堆顶元素放到val里swap(elem,0,usedSize-1); //交换堆顶和堆尾元素shiftDown(0,usedSize-1);//首元素下调usedSize--;}public boolean isEmpty(){return usedSize == 0; //空堆}

2.4.3 堆排序（用堆模拟实现优先级队列）：

思路：

整个 heapSort 方法的核心思路是利用最大堆的特性，通过反复交换堆顶元素和未排序部分的最后一个元素，并进行下沉调整，最终实现一个有序的数组。

具体代码如下：

public void shiftDown2(int parent , int usedSize){ //大根堆int child = 2*parent+1; //获得子树索引while(child< usedSize){if(child+1<usedSize && elem[child]<elem[child+1] ){child++;}if(elem[child] > elem[parent] ){swap(elem,parent,child); //交换双亲结点和孩子节点的位置parent = child; //更新父节点child = 2*parent+1;}else{break;}}}public void heapSort(){int end = usedSize-1;while(end>0){swap(elem,0,end); //交换堆顶堆尾元素shiftDown2(0,end); //交换后将堆顶元素下调end--;//每次迭代减少end，因为最后的元素已经有序}}