优先级队列——二叉堆和最大堆_二叉树建立最大堆heapify

目录

一、优先级队列解释

1、优先级队列的引出

2、优先级队列概念

二、二叉堆

三、基于动态数组实现的最大堆 

1、在最大堆中添加元素

2、在堆中取出最大值

​编辑 3、堆的堆化操作——heapify 

（1）使用堆的添加操作

（2）原地进行headpify操作 

四、相关代码

---

一、优先级队列解释

1、优先级队列的引出

（1）比如说医生根据病情安排手术排期，对于病情相同的情况先来先排，如果有病情较重的，就优先安排手术

（2）对于电脑的操作系统的任务调度来说，系统的任务优先级一般都比普通的应用优先级高

2、优先级队列概念

PriorityQueue(优先级队列主要体现出数据动态化，以及根据要求动态出队)

优先级队列：按照优先级大小动态出队（动态指的是元素的个数动态变化，而非固定）

普通队列：FIFO按照元素的入队顺序，先入先出

二、二叉堆

（1）二叉堆时一颗完全二叉树，基于数组的存储 

 （2）关于节点值

堆的根节点值>=子树的节点值（最大堆，大根堆）

注意:节点的层次和节点的大小没有任何关系，只能保证当前树中，树根是最大值

堆的根节点值<=子树的节点值（最小堆，小根堆）

 （3）因为堆时基于数组存储的，节点之间的下标通过数组的下标来表示

假设某个节点的编号为I:

父节点的编号为parent=(i-1)/2

左子树节点编号为left=2 乘 i +1

右子树节点编号为right=2 乘 i +2

三、基于动态数组实现的最大堆 

package priority_queue;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * 基于动态数组实现的最大堆
 */
public class MaxHeap {
    //实际存储元素的数组
    private List<Integer> elementData;
    //当前堆中的元素个数
    private int size;
 
    public MaxHeap(){
        this(10);
    }
    
    public MaxHeap(int size) {
        elementData = new ArrayList<>();
    }
 
    /**
     * 找到当前节点的父节点的索引
     * @param k
     * @return
     */
    public int parentnode(int k){
        return (k-1)/2;
    }
 
    /**
     * 找到当前节点的左子树节点索引
     * @param k
     * @return
     */