深入理解堆 —— 堆的底层实现，堆排序，TopK问题

短命女 2022-12-05 12:18 205阅读 0赞

## 概念 ##

### 结构特点 ###

堆（数据结构）

*  逻辑上：完全二叉树
 *  物理上：数组

堆是一种顺序存储结构（采用数组方式存储），仅仅是利用完全二叉树的顺序结构的特点进行分析。

### 结点下标计算公式（根节点从0开始） ###

已知二叉树根结点的下标是root,那么它左孩子的下标left=2*root+1，右孩子的下标right=2*root+2。

已知孩子结点的下标（不区分左右）为child，那么双亲的下标为（child-1)/2。

如果从1开始，则已知root，则左孩子节点left=2*root+1,right=2*root+2。已知child，则其根结点root=child/2.

### 堆的定义和性质 ###

*  **小堆** 满足根的值小于等于所有子树结点的值；
 *  **大堆** 根的值大于等于所有子树结点的值。

## 堆的向上，向下调整算法 ##

堆的向下调整算法，当需要调整的节点的左右子树均为大根堆或者小根堆时，就可以使用向下调整算法，通过比较和交换, 让以该节点为首的堆成为一个大根堆或者小根堆。

void AdjustDown(int* a, int root, int n) {
        //建立小堆
    	int parent = root;
    	int child = parent*2+1;
    	while (child < n){
        
    		if (child + 1 < n && a[child] > a[child+1]) {
        
    			child++;
    		}
    		if (a[parent] > a[child]) {
        
    			swap(a[parent], a[child]);
    			parent = child;
    			child = parent*2+1;
    		}else {
        
    			break;
    		}
    	}
    }

堆的向上调整算法，当堆的某个叶子节点位置不满足堆的性质的时候， 那么就可以使用向上调整算法。

void AdjustUp(int* a, int child) {
        //传入当前位置下标   调整小堆
    	int parent = (child-1)/2;
    	while (child > 0) {
        //不能使用parent 意义不明确
    		if (a[child] < a[parent]) {
        
    			swap(a[child], a[parent]);
    			child = parent;
    			parent = (child-1)/2;
    		}else {
        
    			break;
    		}
    	}
    }

## 建堆与堆的删除，插入 ##

有了调整算法我们建堆很简单， 利用向下调整，从倒数第一个非叶子节点向上梳理即可。  
建堆

void CreateHeap(int* a, int n) {
        
    	int parent = (n-2)/2;
    	while (parent >= 0) {
        
    		AdjustDown(a, parent, n);
    		parent--;
    	}
    }

删除堆顶元素

void HeadPop(int* a, int n){
        
    	a[0] = a[n-1];
    	AdjustDown(a, 0, n);
    	//size--; 这里只做简单代码
    }

插入

void HeapInsert(int* a, int n, int x){
        //n代表当前数组已经占用了多少空间
    	a[n] = x;
    	AdjustUp(a, n);
    }

## 堆排序 ##

堆排序首先需要我们将原数组建立为一个堆。因为堆的堆顶元素一定是最大或者最小的， 那么我们每次选出堆顶元素和堆尾元素进行交换，那么就可以达到我们的目的。  
建堆的时间复杂度 O(n)调整的时间复杂度Nlogn  
因此堆排序的时间复杂度是 NlogN  
空间复杂度O(1) 原地排序

void HeapSort(int* a, int n) {
        
    	CreateHeap(a, n);
    	while(n > 0) {
        
    		swap(a[0], a[n-1]]);
    		n--;
    		AdjustDown(a, 0, n);
    	}
    }

## TopK问题 ##

堆作为一种特殊的数据结构， 但是却又不小的用途， 堆排序是一种，另一种就是所谓的topk问题。  
假设有100w个数据， 我们现在要选出最大的十个，有什么方式可以解决。  
1，排序  
2，建100w的大堆。

但是我们却可以建立一个10个元素的小堆， 进行删选。  
具体操作：  
**建立10个元素的小堆， 将100w的数据轮流与堆顶元素比较，比堆顶元素大，则覆盖对顶元素向下调整。**  
从而达到时间复杂度O(n\*logk) 因为k为常数 O(n)  
空间复杂度O(1)