欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

理解堆的操作并实现优先级队列

程序员文章站 2024-02-11 21:16:58
...

堆的操作,最主要的就是向调整向下调整,用这个两个操作来保证堆的性质,最主要的应用有两个。一个是排序算法——堆排序,另一个就是数据结构——优先级队列

什么是堆?

堆其实就是一个完全二叉树,但是它存储在数组里面,利用数组的下标来进行操作结点,数组和堆就是相对应的
理解堆的操作并实现优先级队列
性质
最大堆:每个结点都大于或者等于其两个子结点
最小堆:每个结点都小于或者等于其两个子结点

向上调整和向下调整

这两种操作都是为了维护最大堆或者最小堆的的结构
这里倘若是最大堆
向上调整:某个结点的值大于它的父结点,这时应该将父结点与这个结点进行交换,而当前就是父结点
向下调整:某个结点的值小于它的子结点,这时将子结点和当前结点进行交换,当前这个结点就是子结点

向上调整

 public void shiftUp(int child){
        int parent = (child-1)>>1;
        //向上调整到根节点,就不能在调整
        while (parent >= 0) {
            //父结点小于子结点
            if (arr[parent] < arr[child]) {
                swap(parent, child);
                //较小的孩子和双亲后,可能会导致上层不满足小堆的性质
                child = parent;
                parent = (child - 1) >> 1;
            } else {
                return;
            }
        }
    }

向下调整

public void shifDown(int parent){
	//child标记parent子结点中较大的孩子
	int child = parent*2+1;//默认情况下,先标记左孩子,因为可能不存在右孩子
	int len = arr.length;
	while(child < len){
		//判断是否存在右孩子并符合条件
		if(child + 1 < len && arr[child] < arr[child+1]){
			child+=1;
		}
		if(arr[parent] < arr[child]){
			swap(child,parent);
			//交换之后可能会导致其子树不是大堆结构
			parent = child;
			child = parent*2+1;
		}else{
		    return;
		}
	}
}

优先级队列

这种数据结构,当你插入或者删除数据的时候,元素会自动的排序,其底层的原理就是堆的操作。
插入:insert方法就是先将插入的元素放在堆底的最后,然后进行向上调整,让其调整到正确的位置

  boolean insert(int x){
        //将元素插入到数组中
        array[size++] = x;
        //向上调整
        shiftUp(size-1);
        return true;
    }

删除:poll方法就是先将堆顶元素A和堆底的最后一个元素B进行交换,然后删除A,向下调整B,直到调整到正确的位置

 int poll(){
        int ret = arr[0];
        swap(0,size-1);
        size--;
        shifDown(0);
        return ret;
 }

一个优先级队列就实现了,插入和删除的时间复杂度为O(logN),N为堆的中元素的总数

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法,其实就是一个选择排序(后面的元素已经是有序的,只需要排前面的元素),其时间复杂度为O(nlog n)。
升序(构建大堆),降序(构建小堆)
堆排序的思想
1、先将待排序的元素,利用向下调整的操作构建一个大顶堆;
2、再利用堆删除的思想将堆顶元素和堆底的最后一个元素进行交换,此时末尾就是最大的元素,但是此时堆结构可能已经破坏,从堆顶开始进行向下调整维护堆的结构,再利用堆删除,如此反复执行,直到所有的元素都是有序的

第一步:构建大堆
理解堆的操作并实现优先级队列
第二步:利用堆删除思想,将堆顶元素和堆底的最后一个元素进行交换,此时最后一个元素就是最大的,依次将剩下的元素进行堆的重新构建,如此反复得到的就是一个有序的序列
理解堆的操作并实现优先级队列

相关标签: wen~Structure