堆的概念
- 底层：用数组存储；
- 数据结构：完全二叉树（除了最底层，其它层都必须填满，最后一层可以从左到右填满）；
- 如图：
- 性质：（i对应的是数组的下标）
- 如果当前节点是i，父节点：（i - 1）/ 2;
- 如果当前节点是i，左子树的根节点：2i + 1;
- 如果当前节点是i，右子树的根节点：2i + 2。
堆排序不是稳定的排序算法？
- 在排序过程中，通过heapfity（）的过程涉及到将存在堆最后一个节点跟堆顶节点交换的操作，可能会导致改变相同数据的原始相对顺序。
为什么多数使用快排而不是堆排？
- 堆排序数据访问的方式没有快排友好（对于快速排序来说，数据是顺序访问的，可以很好的利用CPU缓存；堆排序来说，数据是跳转访问的；因为是通过2i + 1, 2i + 2得到子节点的）；
- 堆排的数据交换次数多于快排。
构建大顶堆
方案一：
- 建堆：就是将数组的元素加入到heapInsert（），构造出大顶堆；
- 排序：之后交换首尾数组的位置，将数组长度自减；之后循环的进行heapify（）元素向下移动，再次构造出此时的最大值，之后交换首尾数组的位置，将数组长度自减；
- 其中建堆过程（使用heapInsert()，顺序的遍历元素，涉及元素的上移过程的构造）的时间复杂度为O（nlogn）。
/**
* heapInsertion初始化构造大根堆，通过左右节点与根节点分别比较，如果大于则一直交换当前节点与根节点直到下标为0
* 根节点：(i - 1) / 2;
* 左孩子：2 * i + 1;
* 右孩子：2 * i + 2
*
* @param arr
*/
public static void heapInsertion(int[] arr){
for(int i = 0; i < arr.length; i++){
while((i - 1) / 2 >= 0 && arr[i] > arr[(i - 1) / 2]){
swap(i, (i - 1) / 2, arr);
i = (i - 1) / 2;
}
}
}
方案二（优化）：
- 建堆：优化可以将第一遍构造大顶堆的实现从尾位到首位的遍历，heapInsert（）变化成heapify（）；通过最后一个叶子节点，找到对应的最后一个非叶子节点开始，也就是叶子结点不参与数据下移的过程，因为本身就是叶子节点；所以遍历数组的时候也就省去了（n - 1）/ 2 + 1 到 n 节点的排序；
- 排序：重复方案一的排序过程，交换首尾数组的位置，数组长度自减；循环进行heapify（）。。。。
- 其中建堆过程（使用heapify()，逆序的遍历元素，涉及元素的下移过程的构造）时间复杂度为O（n）；因为完全二叉树的叶子不涉及向下移动。
建堆代码：
/**
* 使用heapify进行构造大根堆，逆序遍历通过最后一个叶子节点找到对应的最后一个非叶子节点，
* 之后从最后一个非叶子节点开始遍历，开始元素的下移，heapify的过程
*
* 时间复杂度为O(n)
* @param arr
*/
public static void heapify(int[] arr){
int n = arr.length;
for(int i = (n - 1) / 2; i >= 0; i--){
heapify(arr, i, n);
}
System.out.println(Arrays.toString(arr));
}
两个重要的概念：heapInsert（）、heapify（）
heapInsert（）
- 构造大顶堆，也就是元素上移过程；同时也是插入数据的过程在数组的最后插入，之后执行元素上移的代码；
- 将左孩子、右孩子与父节点进行比较，如果大于则一直交换当前节点与根节点直到下标为0；如果小于等于不用动。
/**
* heapInsertion初始化构造大根堆，通过左右节点与根节点分别比较，如果大于则一直交换当前节点与根节点直到下标为0
* 根节点：(i - 1) / 2;
* 左孩子：2 * i + 1;
* 右孩子：2 * i + 2
*
* @param arr
*/
public static void heapInsertion(int[] arr){
for(int i = 0; i < arr.length; i++){
while((i - 1) / 2 >= 0 && arr[i] > arr[(i - 1) / 2]){
swap(i, (i - 1) / 2, arr);
i = (i - 1) / 2;
}
}
}
例如：1 4 5 6 7
heapify（）
- 数据下移的过程（已经是大顶堆）；
- 如果拿掉大顶堆的最大值（或者是给定的任意一个位置），也就是数组中首位；将数组中的尾位放入到首位，也就是讲完全二叉树最后一个节点，放到根节点上；
- 如果将左孩子、右孩子的最大值与根节点做比较；如果大于则交换。
/**
*
* @param arr：存储数组
* @param index：给定的未知下标
* @param heapSize：数组长度
*/
public void heapify(int[] arr, int index, int heapSize){
// 如果左孩子的下标小于数组长度，则一定有左孩子
int left = index * 2 + 1;
while(left < heapSize){
// 如果右孩子存在，找到两个孩子最大的下标右孩子（left + 1)
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 找到最大的孩子与父节点的大小
largest = arr[largest] > arr[index] ? largest : index;
// 说明最大值为父节点
if(largest == index){
break;
}
// 交换最大孩子与父节点的值
swap(arr, largest, index);
// 继续向下index的下标到孩子的下标
index = largest;
left = index * 2 + 1;
}
}
应用
优先队列（PriorityQueue）
- 插入一个元素，就是数据上移的过程，也就是heapInsert；
- 删除一个元素，交换首尾数组的元素，将数据下移的过程，也就是heapify。
TopK问题
定义小顶堆实现
代码简洁，无需判断当前元素与堆顶的关系，元素加入又被移除但是涉及数据上移的过程，增加时间复杂度常数O（nlogn）
/**
* topK问题
* 这里的时间复杂度一直为O（nlogn），因为无论不管当前元素是否小于堆顶元素
* 都加入进去，涉及到元素上移的过程；也就是没有剪枝
* @param res
* @param k
*/
public static void sort(int[] res, int k){
// 默认是小顶堆
Queue<Integer> queue = new PriorityQueue<>();
for(int i : res){
queue.offer(i);
if(queue.size() > k){
queue.poll();
}
}
System.out.println("第k大的数：" + queue.peek());
}
剪枝，当堆中元素小于k的时候加入，如果当前元素大于堆顶元素的时候，更新堆顶元素；反之当前元素小于等于堆顶元素的时候，一定不是topK元素，跳过；并不是每个元素都要插入到堆中，进行heapInsert元素上移的过程；所以时间复杂度为O（nlogK）。
/**
* topK问题
* 这里的时间复杂度为O（nlogk），因为当堆中元素已满的时候，会判断堆顶元素和当前元素的大小；
* 如果小于则更新；如果大于等于说明当前元素一定不是TOPK的元素
* @param res
* @param k
*/
public static void optimizeSort(int[] res, int k){
// 默认是小顶堆
Queue<Integer> queue = new PriorityQueue<>();
for(int i : res){
if(queue.size() < k){
queue.offer(i);
}else if(queue.peek() < i){
queue.poll();
queue.offer(i);
}
}
System.out.println("第k大的数：" + queue.peek());
}
快排的partition过程，时间复杂度为O（n）
/**
* topK问题
* 这里的时间复杂度为O（n），通过partition的过程，当基准与len - k重叠的时候返回即可
* @param res
* @param k
*/
public static void quickSort(int[] res, int k){
if(res.length < k){
System.out.println(Arrays.toString(res));
}
int[] arr = new int[k];
quickSort(res, 0, res.length - 1, res.length - k);
System.arraycopy(res, res.length - k, arr, 0, k);
System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] res, int left, int right, int k) {
int index = getIndex(res, left, right);
if(index == k){
return;
}else if(index > k){
quickSort(res, left, index - 1, k);
}else{
quickSort(res, index + 1, right, k);
}
}
private static int getIndex(int[] res, int left, int right) {
int pivot = left;
int index = pivot + 1;
for(int i = index; i <= right; i++){
if(res[i] < res[pivot]){
swap(i, index, res);
index++;
}
}
swap(index - 1, pivot, res);
return index - 1;
}
中位数
class MedianFinder {
Queue<Integer> left;
Queue<Integer> right;
/** initialize your data structure here. */
public MedianFinder() {
left = new PriorityQueue<>((o1, o2) -> (o2 - o1));
right = new PriorityQueue<>();
}
public void addNum(int num) {
if(left.size() == right.size()){
right.offer(num);
left.offer(right.poll());
}else{
left.offer(num);
right.offer(left.poll());
}
}
public double findMedian() {
return left.size() == right.size() ? (left.peek() + right.peek()) / 2.0 : left.peek();
}
}
例题
使用PriorityQueue实现堆的结构、对于不同的数据结构实现不同的初始化；
//小顶堆 new PriorityQueue<>(); //大顶堆 new PriorityQueue<>((o1, o2) -> (o2 - o1)); //字符串小顶堆 new PriorityQueue<>((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
剑指offer41：数据流中的中位数，左侧大顶堆、右侧小顶堆；
class MedianFinder {
// 大顶堆
Queue<Integer> left;
// 小顶堆
Queue<Integer> right;
/** initialize your data structure here. */
public MedianFinder() {
left = new PriorityQueue<>((o1, o2) -> (o2 - o1));
right = new PriorityQueue<>();
}
public void addNum(int num) {
if(left.size() == right.size()){
right.offer(num);
left.offer(right.poll());
}else{
left.offer(num);
right.offer(left.poll());
}
}
public double findMedian() {
return (left.size() == right.size()) ? (left.peek() + right.peek()) / 2.0 : left.peek();
}
}
剑指offer45：把数组排成最小的数
class Solution {
public String minNumber(int[] nums) {
Queue<String> queue = new PriorityQueue<>((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
for(int i : nums){
queue.offer(String.valueOf(i));
}
StringBuffer buffer = new StringBuffer();
while(!queue.isEmpty()){
buffer.append(queue.poll());
}
return buffer.toString();
}
}
例如：剑指offer40，最小的k个数，使用大顶堆实现
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr.length == 0){
return new int[]{};
}
Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> (o2 - o1));
for(int i : arr){
queue.offer(i);
if(queue.size() > k){
queue.poll();
}
}
int[] res = new int[k];
int index = 0;
while(!queue.isEmpty()){
res[index++] = queue.poll();
}
return res;
}
}
TopK问题
- 使用堆排并不是最优解，在面试中书写PriorityQueue容易被挂掉；所以使用快排的思路（partition的过程）实现topK问题；
- 参考链接：https://blog.nowcoder.net/n/22ee0c5d1c5e4e72b2e4ca6b482cbc2c；
- 根据【《算法导论》9.2：期望为线性的选择算法】，可以证明时间负责度为O（n）；
- 例如：剑指offer40，最小的k个数、215. 数组中的第K个最大元素。
具体过程：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr.length <= k){
return arr;
}
int[] res = new int[k];
partition(arr, 0, arr.length - 1, k);
System.arraycopy(arr, 0, res, 0, k);
return res;
}
public void partition(int[] arr, int left, int right, int k){
int index = getIndex(arr, left, right);
if(index == k){
return;
}else if(index < k){
partition(arr, index + 1, right, k);
} else{
partition(arr, left, index - 1, k);
}
}
public int getIndex(int[] arr, int left, int right){
int pivot = left;
int index = pivot + 1;
for(int i = index; i <= right; i++){
if(arr[i] < arr[pivot]){
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
public void swap(int[] arr, int left, int right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
// 快排的partition过程时间负责度为O（n）
return partition(0, nums.length - 1, nums.length - k, nums);
}
public int partition(int left, int right, int k, int[] nums){
int index = getIndex(left, right, nums);
if(index == k){
return nums[k];
}else{
return index < k ? partition(index + 1, right, k, nums) : partition(left, index - 1, k, nums);
}
}
public int getIndex(int left, int right, int[] nums){
int pivot = left;
int index = pivot + 1;
for(int i = index; i <= right; i++){
if(nums[i] < nums[pivot]){
swap(i, index, nums);
index++;
}
}
swap(pivot, index - 1, nums);
return index - 1;
}
public void swap(int left, int right, int[] nums){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
从亿级数据中寻找100个最大的数据？
- 将亿级数据通过hash函数进行分片，分成若干个小文件；
- 在小文件中使用堆排或者快排（partition过程），获取top100；
- 将10个top100的数据放在一起，获取这1000个数据的top100，即是答案。
京公网安备 11010502036488号