【堆排序】优先队列

2024-03-12 18:21:56

优先队列

1、堆

堆，又可以称为二叉堆，可以看做一个近似的完全二叉树，除了最下面一层，其余每层都是填满的，且是从左向右填充。

A表示一个堆，堆的相关概念：
（1）A.length ：数组元素的个数。注意数组中不是所有元素都是有效的。
（2）A.heap-size：数组有效元素的个数，0<=A.heap-size<=A.length
（3）PARENT(i)：给定一个下标 i，它的父节点是 i/2，即

PARENT(i)
	return i/2;

（4）LEFT(i)：给定一个下标 i，它的左孩子节点是 2i

LEFT(i)
	return 2i;

（5）RIGHT(i)：给定一个下标i，它的右孩子节点是 2i+1

RIGHT(i)
	return 2i+1;

堆分为最大堆和最小堆，最大堆是指除了根结点以外，其结点都要满足父结点不小于其本身，即

A[PARENT(i)]>=A[i]

最小堆是指除了根结点以外，其他结点要满足父结点不大于其本身，即

A[PARENT(i)]<=A[i]

对兄弟结点则没有明确要求。

1.1、堆维护

堆维护是指维护堆的性质的过程，用函数 MAX-HEAPIFY （维护最大堆）和 MIN-HEAPIFY （维护最小堆）来表示。比如往当前堆里增加数据或从当前堆里减少数据，都要使改变后的堆依然是最大堆或者最小堆。它的输入是一个数组A 和 下标 i，假设以 LEFT(i) 和 RIGHT(i) 为根结点的树都满足最大堆或者最小堆的性质，现在需要维护以 i 下标元素为根结点的子树满足最大堆或最小堆性质。

维护最大堆的伪代码如下：

MAX-HEAPIFY(A,i):
	# 对比当前结点与其左孩子、右孩子的值的大小，大的调整为父结点
	l = LEFT(i);
	r = RIGHT(i);
	# largest用于记录比较二者的较大值
	largest = [i]
	# 比较左孩子的值和当前值，如果左孩子的值大，令 largest为左孩子的下标
	if l<=A.heap.size and A[l]>A[largest]
		largest = l;
	# 比较largest和右孩子的值，如果右孩子的值大，令 largest为右孩子的下标
	if r<=A.heap.size and A[r]>A[largest]
		largest = r;
	# 如果 i 和 largest 不等，说明发生了变动，根结点和largest对应的结点交换
	if i ≠ largest
		exchange A[i] and A[largest];
		MAX-HEAPIFY(A,largest);

最小堆的维护过程：

MIN-HEAPIFY(A,i):
	l = LEFT(i);
	r = RIGHT(i);
	smallest = i;
	if l<=A.heap-size && A[l]<A[smallest]
		smallest = l;
	if r<=A.heap-size && A[r]<A[smallest]
		smallest = r;
	if i ≠ smallest
		exchange A[i] and A[smallest];
		MIN-HEAPIFY(A,smallest)

注意堆维护函数的大前提：以 LEFT(i) 和 RIGHT(i) 为根结点的树都满足最大堆或者最小堆的性质。只有满足了这个前提条件，比较 A[i] 与 A[LEFT(i)]、A[RIGHT(i)]才有意义

1.2、建堆

知道怎么维护堆以后就可以开始建堆。
建堆可以调用堆维护函数，建堆伪代码如下：

BUILD-MAX-HEAP(A):
	A.heap-size = A.length;
	for i = ⌊A.heap-size/2⌋; i>=1; i--
		MAX-HEAPIFY(A,i)

这里为什么要从下标为 ⌊A.heap-size/2⌋ 的结点开始维护？因为使用堆维护函数的一个前提就是输入的下标 i 的左右子树都满足最大堆或者最小堆的性质。这里要用堆维护函数，就得保证从最底层往上的第一个拥有子树的结点的左右子树满足最大堆或最小堆的性质，所以要从最底层往上的第一个拥有子树的结点开始维护，而这个结点的下标就是 ⌊A.heap-size/2⌋
同理，最小堆的建堆函数为

BUILD-MIN-HEAP(A):
	A.heap-size = A.length;
	for i = ⌊A.heap-size/2⌋; i>=1; i--
		MIN-HEAPIFY(A,i)

2、优先队列

优先队列是一种用来维护一族元素构成的集合的数据结构，它的底层数据结构可以用二叉堆实现。它提供的操作有：
（1）INSERT(A,x): 把元素x插入A中
（2）MAXIMUM(A) / MINIMUM(A): 返回A中最大/最小元素
（3）EXTRACT-MAX(A) / EXTRACT-MIN(A): 返回并删除A中最大/最小元素
（4）INCREASING(A,x,key) / DEREASING(A,x,key) : 把A中元素x的值增加/减少至key

如果底层用了二叉堆这种数据结构，那么上面的操作就很好实现了。因为A满足了最大堆或最小堆的性质，那么根结点就是A中最大元素或者最小元素

MAXIMUM(A) / MINIMUM(A):

HEAP-MAXIMUM(A):
	return A[1]

HEAP-MINIMUM(A):
	return A[1]

EXTRACT-MAX(A) / EXTRACT-MIN(A):

HEAP-EXTRACT-MAX(A):
	if A.heap-size<1
		error;
	max = A[1];
	A[1] = A[A.heap-size];
	A.heap-size--;
	MAX-HEAPIFY(A,1);
	return max

HEAP-EXTRACT-MIN(A):
	if A.heap-size<1
		error;
	min = A[1];
	A[1] = A[A.heap-size];
	A.heap-size--;
	MIN-HEAPIFY(A,1);
	return min

INCREASING(A,x,key) / DEREASING(A,x,key) :

HEAP-INCREASING(A,x,key):
	A[x] = key;
	while(x>1&&A[x]>A[PAREMT(x)])
		交换A[x]和A[PAREMT(x)];
		x = PAREMT(x);

HEAP-DECREASING(A,x,key):
	A[x] = key;
	while(x>1&&A[x]<A[PAREMT(x)])
		交换A[x]和A[PAREMT(x)];
		x = PAREMT(x);

INSERT(A,x):

# 插入最大堆
HEAP-MAX-INSERT(A,x):
	A.heap-size++;
	A[A.heap-size] = -∞;
	HEAP-INCREASING(A,A.heap-size,x):

# 插入最小堆
MIN-INSERT(A,x):
	A.heap-size++;
	A[A.heap-size] = +∞;
	HEAP-DECREASING(A,A.heap-size,x):

3、代码实现

以下的代码假设数组A为ArrayList类型，其实用泛型写更好一点。

3.1、最大堆

维护堆性质：

public void MaxHeapIFY(List<Integer>nums,int i){
        left = i*2+1;
        right = i*2+2;
        int largest = i;
        if( left<nums.size()&&nums.get(left)>nums.get(largest) ){
            largest = left;
        }
        if( right<nums.size()&&nums.get(right)>nums.get(largest)){
            largest = right;
        }
        if( largest!=i ){
            int temp = nums.get(largest);
            nums.set(largest,nums.get(i));
            nums.set(i,temp);
            MaxHeapIFY(nums,largest);
        }
    }

建堆：

 public List<Integer> BuildMaxHeap(List<Integer>nums){
        if(nums.size()<1){
            return null;
        }
        int begin = nums.size()/2-1;
        for( int i=begin;i>=0;i--){
            MaxHeapIFY(nums,i);
        }
        return nums;
    }

3.2、最小堆

（1）维护堆性质：

public void minHeapIFY(List<Integer> nums, int i){
        left = i*2+1;
        right = left+1;
        int smallest = i;
        if( left<nums.size() && nums.get(left)<nums.get(smallest) ){
            smallest = left;
        }
        if( right<nums.size() && nums.get(right)<nums.get(smallest) ){
            smallest = right;
        }
        if( smallest!=i ){
            int temp = nums.get(smallest);
            nums.set(smallest,nums.get(i));
            nums.set(i,temp);
            minHeapIFY(nums,smallest);
        }
}

建堆：

public void buildMinHeap(List<Integer> nums){
        if(nums.size()<1){
           return ;
        }
        int begin = nums.size()/2+1;
        for(int i=begin; i>=0; i--){
            minHeapIFY(nums,i);
        }
}

3.3、优先队列

（1）返回最大值

public int getMaxValue(List<Integer>nums){
	MyMaxHeap maxHeap = new MyMaxHeap();
	maxHeap.BuildMaxHeap(nums);
	return nums.get(0);
}

（2）返回最小值

public int getMinValue(List<Integer>nums){
	MyMinHeap minHeap = new MyMinHeap();
	minHeap.buildMinHeap(nums);
	return nums.get(0);
}

（3）返回并删除最大值

public int extractMaxValue(List<Integer>nums){
       MyMaxHeap maxHeap = new MyMaxHeap();
       maxHeap.BuildMaxHeap(nums);
       int max = nums.get(0);
       if(nums.size()>0){
           nums.set(0,nums.get(nums.size()-1));
           nums.remove(nums.size()-1);
           maxHeap.MaxHeapIFY(nums,0);
           return max;
       }
       nums.remove(nums.size()-1);
       return max;
}

（4）返回并删除最小值

public int extractMinValue(List<Integer>nums){
       MyMinHeap minHeap = new MyMinHeap();
       minHeap.buildMinHeap(nums);
       int min = nums.get(0);
       if(nums.size()>0){
           nums.set(0,nums.get(nums.size()-1));
           nums.remove(nums.size()-1);
           minHeap.minHeapIFY(nums,0);
           return min;
       }
       nums.remove(nums.size()-1);
       return min;
}

（5）将下标为 i 的元素值提升为key

public void increasing(List<Integer>nums,int i, int key){
       if( i>nums.size()-1 ){
           return;
       }
       if( nums.get(i)>key ){
           return;
       }
       nums.set(i,key);
       MyMaxHeap maxHeap = new MyMaxHeap();
       maxHeap.BuildMaxHeap(nums);
       maxHeap.MaxHeapIFY(nums,i);
}

（6）将下标为 i 的元素值减少为key

public void decreasing(List<Integer>nums,int i, int key){
        if( i>nums.size()-1 ){
            return;
        }
        if( nums.get(i)<key ){
            return;
        }
        nums.set(i,key);
        MyMinHeap minHeap = new MyMinHeap();
        minHeap.buildMinHeap(nums);
        minHeap.minHeapIFY(nums,i);
}

（7）增加一个数（最大堆）

public void insertMaxHeap(List<Integer>nums,int key){
       nums.add(Integer.MIN_VALUE);
       increasing(nums,nums.size()-1,key);
}

（8）增加一个数（最小堆）

public void insertMinHeap(List<Integer>nums,int key){
        nums.add(Integer.MAX_VALUE);
        decreasing(nums,nums.size()-1,key);
}
上一篇：ognl


下一篇：使用mybatis 过程中遇到的报错的坑