JZTXT

堆结构和堆排序

发布时间 2023-12-17 09:41:59作者: lwj1239

堆

堆是一种特殊的完全二叉树，其他语言中的优先级队列就是堆。堆分为大根堆和小根堆，大根堆即对于每一颗树，它的父亲节点的值，一定大于它的孩子节点的值，左右节点的值不用管它的顺序。小根堆同理。

堆的实现通常是用数组实现的，那么对于每一个节点在数组中怎么找到它的父节点和它的左右孩子就成了一个问题。

那么对于任意一个节点i，它的父节点在数组中的表示为(i - 1) / 2，它的左孩子为2 * i + 1，它的右孩子为2 * i + 2。

那么堆最主要的就两个操作，在堆中插入一个节点和在堆中删掉一个节点。

在堆中插入一个节点，也就是把要插入的元素放在数组的末尾，再往上调整。

代码实现

void heapinsert(ELEMENT *a, int index)//把下标index的值插入到堆中 
{
	while(a[index] > a[(index - 1) / 2])//如果下标index的值大于它的父节点 
	{
		swap(a, index, (index - 1) / 2);//下标index的值和它的父节点的值交换 
		index = (index - 1) / 2;//更新index的位置 
	}
}

在堆中删除一个节点，就是把树根的值取出，再把堆中最后一个元素放在树根，再向下调整。

代码实现

void heapify(ELEMENT *a, int index, int heapSize)//index位置的数变小了，又想维持大根堆结构，向下调整大根堆 
{
	int left = 2 *index + 1;//下标index的左孩子 
	
	while(left < heapSize)//只要还有孩子 
	{
		int largest = left + 1 < heapSize && a[left + 1] > a[left]? left + 1: left;//如果有右孩子并且右孩子的值大于左孩子的值，那么右孩子就是最大的，否则就是左孩子最大 
		
		largest = a[largest] > a[index]? largest:index;//如果左右孩子中最大的比父节点大，那么最大的还是它，没有父节点大，那么最大的是父节点 
		
		if (largest == index) {//如果最大的是父节点，那么不用调整了，是大根堆了 
			break;
		}
		
		swap(a, largest, index);//父节点与左右孩子中最大的做交换 
		index = largest;//更新index 
		left = index * 2 + 1;//重新计算左孩子的位置 
	}
}

堆排序

堆排序的时间复杂度是O(N * logN),它就是把数组转化成一个堆之后，再每次把堆的第一个元素放在一个需要放的位置，然后调整堆。当堆中只有一个元素之后就已经排好序了。

也就是分为了两个步骤，第一步建立一个堆，第二步在删除堆顶元素之后调整堆。

调整过程的时间复杂度是O(N * logN),这是无法再改变的。

但建立堆的是时间复杂度可以做到O(N),建立堆分为从顶建堆和从底建堆。

从顶建堆的时间复杂度是O(N * logN)。

//从顶建堆
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 100000

typedef int ELEMENT;

void heapSort(int *a, int size);
void heapinsert(int *a, int index);
void heapify(int *a, int index, int heapSize);
void swap(int *a, int i, int j);

int main() {
    int a[N];
    
    srand(time(NULL));
    
    int n;
	
	scanf("%d", &n);
    
    for (int i = 0; i < N; i++){
		scanf("%d", a + i);
	}
	
	heapSort(a, n);

	for (int i = 0; i < n; i++){
    	printf("%d ", a[i]);
	}
	
	putchar('\n');

    return 0;
}
void heapSort(ELEMENT *a, int size)
{
	if (a == NULL || size == 2){
		return ;
	}
	
	int heapSize = size;
	
	for (int i = 0; i < size; i++)//从顶建立一个大根堆 
	{
		heapinsert(a, i);
	}
	
	swap(a, 0, --heapSize);//把堆的第一个元素与堆的最后一个元素交换，然后堆的大小减一 
	
	while(heapSize > 1){//只要堆中的元素大于1 
		heapify(a, 0, heapSize);//因为0位置的数变小了，向下调整大根堆 
		swap(a, 0, --heapSize);//把堆的第一个元素与堆的最后一个元素交换，然后堆的大小减一 
	}
}
void heapinsert(ELEMENT *a, int index)//index位置的数向上调整大根堆 
{
	while(a[index] > a[(index - 1) / 2])//如果下标index的值大于它的父节点 
	{
		swap(a, index, (index - 1) / 2);//下标index的值和它的父节点的值交换 
		index = (index - 1) / 2;//更新index的位置 
	}
}
void heapify(ELEMENT *a, int index, int heapSize)//index位置的数变小了，又想维持大根堆结构，向下调整大根堆 
{
	int left = 2 *index + 1;//下标index的左孩子 
	
	while(left < heapSize)//只要还有孩子 
	{
		int largest = left + 1 < heapSize && a[left + 1] > a[left]? left + 1: left;//如果有右孩子并且右孩子的值大于左孩子的值，那么右孩子就是最大的，否则就是左孩子最大 
		
		largest = a[largest] > a[index]? largest:index;//如果左右孩子中最大的比父节点大，那么最大的还是它，没有父节点大，那么最大的是父节点 
		
		if (largest == index) {//如果最大的是父节点，那么不用调整了，是大根堆了 
			break;
		}
		
		swap(a, largest, index);//父节点与左右孩子中最大的做交换 
		index = largest;//更新index 
		left = index * 2 + 1;//重新计算左孩子的位置 
	}
}
void swap(ELEMENT *a, int i, int j)
{
	ELEMENT t = a[i];
	a[i] = a[j];
	a[j] = t;
}

从底建堆的时间复杂度是O(N),因为它调整的次数变少了。

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 100000

typedef int ELEMENT;

void heapSort(int *a, int size);
void heapinsert(int *a, int index);
void heapify(int *a, int index, int heapSize);
void swap(int *a, int i, int j);

int main() {
    int a[N];
    
    srand(time(NULL));
    
    int n;
	
	scanf("%d", &n);
    
    for (int i = 0; i < N; i++){
		scanf("%d", a + i);
	}
	
	heapSort(a, n);

	for (int i = 0; i < n; i++){
    	printf("%d ", a[i]);
	}
	
	putchar('\n');

    return 0;
}
void heapSort(ELEMENT *a, int size)
{
	if (a == NULL || size == 2){
		return ;
	}
	
	int heapSize = size;
	
	for (int i = size - 1; i >= 0; i--)//从底建立一个大根堆 
	{
		heapify(a, i, size);
	}
	
	swap(a, 0, --heapSize);//把堆的第一个元素与堆的最后一个元素交换，然后堆的大小减一 
	
	while(heapSize > 1){//只要堆中的元素大于1 
		heapify(a, 0, heapSize);//因为0位置的数变小了，向下调整大根堆 
		swap(a, 0, --heapSize);//把堆的第一个元素与堆的最后一个元素交换，然后堆的大小减一 
	}
}
void heapinsert(ELEMENT *a, int index)//index位置的数向上调整大根堆 
{
	while(a[index] > a[(index - 1) / 2])//如果下标index的值大于它的父节点 
	{
		swap(a, index, (index - 1) / 2);//下标index的值和它的父节点的值交换 
		index = (index - 1) / 2;//更新index的位置 
	}
}
void heapify(ELEMENT *a, int index, int heapSize)//index位置的数变小了，又想维持大根堆结构，向下调整大根堆 
{
	int left = 2 *index + 1;//下标index的左孩子 
	
	while(left < heapSize)//只要还有孩子 
	{
		int largest = left + 1 < heapSize && a[left + 1] > a[left]? left + 1: left;//如果有右孩子并且右孩子的值大于左孩子的值，那么右孩子就是最大的，否则就是左孩子最大 
		
		largest = a[largest] > a[index]? largest:index;//如果左右孩子中最大的比父节点大，那么最大的还是它，没有父节点大，那么最大的是父节点 
		
		if (largest == index) {//如果最大的是父节点，那么不用调整了，是大根堆了 
			break;
		}
		
		swap(a, largest, index);//父节点与左右孩子中最大的做交换 
		index = largest;//更新index 
		left = index * 2 + 1;//重新计算左孩子的位置 
	}
}
void swap(ELEMENT *a, int i, int j)
{
	ELEMENT t = a[i];
	a[i] = a[j];
	a[j] = t;
}