堆及其相关操作

浅浅的花香味﹌ 2022-05-05 04:58 243阅读 0赞

### 文章目录 ###

*   *  堆
     *  向下调整
     *  堆的创建
     *   *   *  大堆
             *  小堆
     *  堆的初始化
     *  堆顶元素
     *  堆的插入
     *  堆的删除
     *  向上调整
     *  TopK

## 堆 ##

堆，也叫做二叉堆。  
目的：在堆中找到最值（最大值、最小值）  
      堆顶存放的不是最大值就是最小值  
**堆是已数组的形式存储的，但在逻辑上是完全二叉树**  
例如：

int arr[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };

对应的堆为：  
![在这里插入图片描述][70]  
注：上述堆还未进行调整

typedef int DataType;
    	//堆的结构体
    	typedef struct Heap
    	{
    		DataType arr[MAX_SIZE];
    		int size;
    	}Heap;

## 向下调整 ##

如果一个结点的下标为root，则  
    左孩子：root \* 2 + 1

右孩子：root \* 2 + 2

父结点：(root - 1) / 2  
![在这里插入图片描述][70 1]

void Swap(int *pa, int *pb)
    	{
    		int tmp = *pa;
    		*pa = *pb;
    		*pb = tmp;
    	}
    	//size表示数组元素个数，root要调整元素的下标
    	void AdjustDown(DataType arr[], int size, int root)
    	{
    		while (1)
    		{
    			int left = root * 2 + 1;
    			int right = root * 2 + 2;
    			if (left >= size)
    			{
    				return;
    			}
    			int max = left;
    			if (right < size && arr[right] > arr[max])
    			{
    				max = right;
    			}
    			if (arr[max] < arr[root])
    			{
    				return;
    			}
    			Swap(arr + max, arr + root);
    			root = max;
    		}
    	}

## 堆的创建 ##

#### 大堆 ####

void CreateHeap(DataType arr[], int size)
    	{
    		//因为要找到最后一个叶子结点的父结点进行调整，所以i从(size - 2) / 2开始
    		for (int i = (size - 2) / 2; i >= 0; i--)
    		{
    			AdjustDown(arr, size, i);
    		}
    	}

#### 小堆 ####

void AdjustDownSmall(DataType arr[], int size, int root)
    	{
    		while (root * 2 + 1 < size)
    		{
    			int min;
    			if ((root * 2 + 2 < size) && (arr[root * 2 + 2] < arr[root * 2 + 1]))
    			{
    				min = root * 2 + 2;
    			}
    			else
    			{
    				min = root * 2 + 1;
    			}
    			if (arr[root] < arr[min])
    			{
    				return;
    			}
    			Swap(&arr[root], &arr[min]);
    			root = min;
    		}
    	}
    	//
    	void CreateHeapSmall(DataType arr[], int size)
    	{
    		//因为要找到最后一个叶子结点的父结点进行调整，所以i从(size - 2) / 2开始
    		for (int i = (size - 2) / 2; i >= 0; i--)
    		{
    			AdjustDownSmall(arr, size, i);
    		}
    	}

## 堆的初始化 ##

//ph->arr表示调整后的数组，arr表示原来的数组，size表示数组元素的个数
    	void HeapInit(Heap *ph, DataType arr[], int size)
    	{
    		assert(size <= MAX_SIZE);
    		memcpy(ph->arr, arr, sizeof(DataType) * size);
    		ph->size = size;
    	
    		CreateHeapSmall(ph->arr, ph->size);
    	}

## 堆顶元素 ##

DataType HeapTop(Heap *ph)
    	{
    		assert(ph->size > 0);
    		return ph->arr[0];
    	}

## 堆的插入 ##

规则：在最后一个叶子结点后面在插入一个结点，然后进行调整

void HeapPush(Heap *ph, DataType data)
    	{
    		assert(ph->size < 100);
    		ph->arr[ph->size] = data;
    		ph->size++;
    		AdjustDown(ph->arr, ph->size, (ph->size - 2) / 2);
    	}

## 堆的删除 ##

规则：删除堆顶元素，将最后一个叶子结点放在堆顶，进行调整

void HeapPop(Heap *ph)
    	{
    		assert(ph->size > 0);
    		ph->arr[0] = ph->arr[ph->size - 1];
    		ph->size--;
    		AdjustDown(ph->arr, ph->size, 0);
    	}

## 向上调整 ##

void AdjustUpBig(DataType arr[], int size, int child)
    	{
    		while (child > 0)
    		{
    			int parent = (child - 1) / 2;
    			if (arr[child] < arr[parent])
    			{
    				return;
    			}
    			Swap(arr + child, arr + parent);
    			child = parent;
    		}
    	}

**注：向上调整是知道孩子结点，查询父结点开始调整  
    向下调整是知道父节点，查询孩子结点开始调整**

## TopK ##

查询一组数据中，前K个最大的元素  
第一步：取前K个元素出来，创建一个只有K个元素的小堆  
第二步：将堆顶元素与剩下的元素一一比较，  
        堆顶元素大：return  
        堆顶元素小：将堆顶元素更换，进行调整

void HeapTopK(DataType arr[], int size, int k)
    	{
    		int *heap = (int *)malloc(k * sizeof(int));
    		for (int i = 0; i < k; i++)
    		{
    			heap[i] = arr[i];
    		}
    		CreateHeapSmall(heap, k);
    		for (int i = k; i < size; i++)
    		{
    			if (arr[i] < heap[0])
    			{
    				continue;
    			}
    			heap[0] = arr[i];
    			AdjustDownSmall(heap, k, 0);
    		}
    	
    		for (int i = 0; i < k; i++)
    		{
    			printf("%d ", heap[i]);
    		}
    		free(heap);
    	}

**注：上述所有的root都表示下标，在堆中只是用到了二叉树的思想，但真正的还是操作数组，一定不能出现root->left的情况**

[70]: /images/20220505/ff1905d488c64120a395f8066ef1f32a.png
[70 1]: /images/20220505/dceff0b12bab42158e584515bad9435f.png