排序——堆排序和TopK

灰太狼 2022-02-25 14:24 180阅读 0赞

## 前言 ##

堆排序与TopK的问题，面试中还是经常问的，索性也整理一下。下面是徒手写的，供参考.

## 堆排序 ##

#### 思路 ####

堆的数据结构，本身就是一个二叉树，二叉树的每一个根节点始终大于两个孩子的值，这就是大顶堆；如果始终小于两个孩子节点的值，这就是小顶堆。  
堆排序的操作方式：先构造一个大顶堆，这样我们就知道了最大的值，然后将最大值和数组的最后一个元素交换，然后重新调整堆，这样我们就确定新堆的最大值（第二大），再和数组的倒数第二个元素进行交换。如此循环，知道全部排好。  
构造堆的方式，是利用下沉方法进行的，通过对数组前一半的元素进行下沉即可构造一个堆，因为只有前一半的节点才有子节点。

#### 实现 ####

public void heapSort(int[] array) { 
    	// 先构造一个大顶堆
    	int N = array.length - 1;
    	for (int i = (N - 1) / 2; i >= 0; i--) { 
    		sink(array, i, N);
    	}
    
    	// 每次将堆顶元素替换至末尾
    	for (int i = N; i > 0; i--) { 
    		swap(array, 0, i);  // 堆顶元素交换至末尾
    		sink(array, 0, i - 1);  // 重新下沉
    	}
    }
    
    public void sink(int[] array, int k, int tail) { 
    	while (2 * k + 1 <= tail) { 
    		int index = 2 * k + 1;
    		if (index < tail && array[index] < array[index + 1]) // 大顶堆逻辑
    			index = 2 * k + 2;
    		if (array[k] >= array[index])
    			break;
    		swap(array, k, index);
    		k = index;
    	}
    }
    
    public void swap(int[] array, int i, int j) { 
    	int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

## TopK问题 ##

#### 思路 ####

创建一个小顶堆，堆的元素个数为 `k`，然后进行遍历超大数组，每次过来一个元素和堆顶相比，比堆顶小或者等于可以确定非TopK元素，如果比堆顶元素大，则替换堆顶元素，并进行调整堆结构，如此循环往复…

#### 实现 ####

public int[] topK(int[] array, int k) { 
    	int[] res = new int[k];
    
    	// 复制k个元素
    	for (int i = 0; i < k; i++) { 
    		res[i] = array[i];
    	}
    
    	// 构造一个小顶堆
    	for (int i = (k - 2) / 2; i >= 0; i--) { 
    		sink(res, i, k - 1);
    	}
    	
    	// 然后遍历array数组，每次和堆顶元素比较，如果大于就替换堆顶并下沉
    	for (int i = k; i < array.length; i++) { 
    		if (array[i] > res[0]) { 
    			res[0] = array[i];
    			sink(res, 0, k - 1);
    		}
    	}
    	return res;
    }
    
    public void sink(int[] array, int k, int tail) { 
    	while (2 * k + 1 <= tail) { 
    		int index = 2 * k + 1;
    		if (index < tail && array[index] > array[index + 1]) // 小顶堆逻辑
    			index = 2 * k + 2;
    		if (array[k] <= array[index])
    			break;
    		swap(array, k, index);
    		k = index;
    	}
    }