一、堆结构的定义

堆通常是一个可以被看做一棵 完全二叉树的数组对象，堆是非线性数据结构。堆总是满足下列性质：

堆中的某个节点的值总是不大于或者不小于其父节点的值
堆总是一个完全二叉树

倘若子树中子节点中的值都小于父节点那么这个堆称为小根堆，反之称为大根堆

二、堆的实现、

2.1 堆的向上调整算法

2.1.1 思路

数组中新添加进来的元素，与自己的父元素比较若比自己的父元素大则交换，一直比到索引为 0 或者直到此元素没有自己的父元素大为止

public void heapInsert(int[] arr, int index) {

while (arr[index] > arr[(index - 1) / 2]) {

swap(arr, index, (index - 1) / 2);

index = (index - 1) / 2;

}

堆的向下调整算法

2.2.1 思路

数组是一个堆，从某个指定的位置开始和自己的左右两个叶节点比较如果这个位置比某个叶子节点小就交换，直到不比叶子节点小为止，或者已经到了堆的最后位置。

public void heapify(int[] arr, int index, int heapSize) {

int left = index << 1 + 1;

while (left < heapSize) {

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 = largest;

left = index << 1 + 1;

}

2.3 堆结构完整代码

import lombok.Data;

import java.util.Arrays;

@Data

public class Code01_Heap {

/**

* 堆的实现

private int[] heap;

/**

* 堆中元素的个数

private int heapSize;

/**

* 容量

private int capacity;

public Code01_Heap(int capacity) {

this.capacity = capacity;

this.heap = new int[capacity];

this.heapSize = 0;

}

/**

* 判断堆是否为空

* @return true:为空 false:不为空

public boolean isEmpty() {

return heapSize == 0;

}

/**

* 判断堆是否满了

* @return true:满了 false:没满

public boolean isFull() {

return heapSize == capacity;

}

public void push(int value) {

if (isFull()) {

throw new RuntimeException("堆满了");

}

heap[heapSize] = value;

heapInsert(heap, heapSize++);

}

public int pop() {

if (isEmpty()) {

throw new RuntimeException("堆为空");

}

int ans = heap[0];

heap[0] = heap[--heapSize];

heapify(heap, 0, heapSize);

return ans;

}

public int peek() {

if (isEmpty()) {

throw new RuntimeException("堆为空");

}

return heap[0];

}

public void heapify(int[] arr, int index, int heapSize) {

int left = index << 1 + 1;

while (left < heapSize) {

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 = largest;

left = index << 1 + 1;

}

public void heapInsert(int[] arr, int index) {

while (arr[index] > arr[(index - 1) / 2]) {

swap(arr, index, (index - 1) / 2);

index = (index - 1) / 2;

}

private void swap(int[] arr, int i, int j) {

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

public static void main(String[] args) {

System.out.println(-1 / 2);

Code01_Heap heap = new Code01_Heap(10);

heap.push(3);

heap.push(1);

heap.push(5);

System.out.println(Arrays.toString(heap.getHeap()));

}

三、堆排序

3.1 思路

heapSort 方法：
首先，如果数组为空或者只有一个元素，那么无需排序，直接返回。
然后，使用 heapify 方法从最后一个非叶子节点开始，向前遍历数组，将每个子树调整为大根堆。这一步的目的是将数组初始化为大根堆。
在数组被初始化为大根堆之后，开始排序过程。每次将堆顶元素（最大元素）与当前堆的最后一个元素交换，然后将堆的大小减1，并重新调整堆。重复这个过程直到堆的大小为0，此时数组已经排序完成。
heapify 方法：
该方法用于调整以 i 为根节点的子树为最大堆。
首先，计算左子节点的索引 left。
然后，进入一个循环，在该循环中，找到 i、左子节点和右子节点中的最大值。
如果最大值不是 i，那么将最大值与 i 交换，并更新 i 和 left 的值，继续循环。
如果最大值就是 i，那么退出循环，此时以 i 为根节点的子树已经是一个最大堆。
heapInsert 方法：
这个方法用于在构建堆的过程中，将新插入的元素插入到正确的位置，以保持堆的性质。但是在这段代码中，heapInsert 方法并没有在 heapSort 方法中被调用，因此这段代码中的 heapInsert 是多余的。也可以使用heapInsert 方法初始化堆结构。
swap 方法：
这个方法用于交换数组中的两个元素。

3.2 代码

package com.zhang.study.chapter06;

import java.util.Arrays;

import static com.zhang.util.RandomArrayUtil.generateRandomArray;

/**

* 堆排序

public class Code02_HeapSort {

public static void heapSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

// O(N*logN)

// for (int i = 0; i < arr.length; i++) {

// heapInsert(arr, i);

// }

// O(N)

for (int i = arr.length - 1; i >= 0; i--) {

heapify(arr, i, arr.length);

}

int size = arr.length;

// O(N*logN)

while (size > 0) { // O(N)

swap(arr, 0, --size); // O(1)

heapify(arr, 0, size); // O(logN)

}

private static void heapify(int[] arr, int i, int size) {

int left = i * 2 + 1;

while (left < size) {

int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;

largest = arr[largest] > arr[i] ? largest : i;

if (largest == i) {

break;

}

swap(arr, largest, i);

i = largest;

left = i * 2 + 1;

}

private static void heapInsert(int[] arr, int index) {

while (arr[index] > arr[(index - 1) / 2]) {

swap(arr, index, (index - 1) / 2);

index = (index - 1) / 2;

}

private static void swap(int[] arr, int index, int i) {

int temp = arr[index];

arr[index] = arr[i];

arr[i] = temp;

}

public static void main(String[] args) {

int maxSize = 100;

int maxValue = 1000;

int testTime = 500000;

for (int i = 0; i < testTime; i++) {

int[] arr1 = generateRandomArray(maxSize, maxValue);

int[] arr2 = arr1.clone();

heapSort(arr1);

Arrays.sort(arr2);

if (!Arrays.equals(arr1, arr2)) {

System.out.println("Oops!");

return;

}

System.out.println("Nice!");

}

四、堆排序的时间复杂度

堆排序的时间复杂度是 (N*logN)

public static void heapSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

// O(N*logN)

// for (int i = 0; i < arr.length; i++) {

// heapInsert(arr, i);

// }

// O(N)

for (int i = arr.length - 1; i >= 0; i--) {

heapify(arr, i, arr.length);

}

int size = arr.length;

// O(N*logN)

while (size > 0) { // O(N)

swap(arr, 0, --size); // O(1)

heapify(arr, 0, size); // O(logN)

}

倘若是使用 heapInsert 来插入元素，则是这个 for 循环是O(N*logN)，这个操作是将数组转为大根堆

for (int i = 0; i < arr.length; i++) {

heapInsert(arr, i);

}

因为每次插入一个元素需要和自己的父元素作比较，每次比较是 logN级别的所以是(N*logN)

但是这个操作如果数组是一次性全部拿到而不是一个一个给的，是可以收敛为O(N)的。

我们可以把这个数组直接想象成为一个完全二叉树，虽然它不是大根堆。例如：

我们想象这个数组就是完全二叉树，然后从下往上遍历，依次是 76 43 5 43 12 32 22 43，依次进行heapify 最后一层就变成了大根堆，然后再遍历89 23 344 13 依然是heapify 这样倒数第二层以及最后一层都是大根堆，然后依次12 21、10这样下来数组就变成了大根堆的结构。这个操作的时间复杂度是O(N)。为什么呢？

假设数组有 N 个元素，那么叶节点差不多就有N/2个也就是最下面一层，刚刚上述数组有 15 个元素叶节点有 8 个，即使不是完全满二叉树也是一样的，例如下图：有四个元素，叶节点有两个

这些节点在做heapify 时候，只需要判断自己，N/2 * 1，倒数第二层的节点从数量级来说大概是有N/4个在做heapify时候，最多需要判断三个单位往下沉的的次数和层数有关，所以是N/4 * 2

那么第三层有N/8个节点，最多需要判断加交换N/8 * 6次

整个时间复杂度 T(N) = N/2 * 1 + N/4 * 2 + N/8 * 4 + N/16 * 6 +...... 相乘后忽略常数项的时间复杂度是 O(N)这个是里面所有操作的时间复杂度。

五、面试题

5.1 题目一

已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。

举例：

原始数组 arr = [3,4,1,2,5] k = 2

排序后数组 arr = [1,2,3,4,5]

1 排序后从索引为 2 的位置到索引为 0 的位置移动了两个位置

2 排序后从索引为 3 位置移动到索引为 1 的位置移动了两个位置

3 排序后从索引为0 位置移动到索引 2 的位置移动了两个位置

4 排序后从索引为 1 移动到索引索引 3 的位置移动了两个位置

5 排序后从索引为 4 的位置移动索引为 4 的位置移动了零个位置

5.1.1 思路

可以使用小根堆，先将数组的前 k 个值放入小根堆中每次弹出的就是最小值然后弹出一个值再放入一个值，最后将小根堆中的值全部弹出。时间复杂度为O(N*logK)k 比 N 小就是最优解

5.1.2 代码

import java.util.Arrays;

import java.util.PriorityQueue;

public class Code03_SortArrayDistanceLessK {

public static void sortedArrDistanceLessK(int[] arr, int k) {

if (arr == null || arr.length < 2 || k < 1) {

return;

}

// 默认是小根堆

PriorityQueue<Integer> queue = new PriorityQueue<>();

int index = 0;

for (index = 0; index < Math.min(arr.length , k ); index++) {

queue.add(arr[index]);

}

int i = 0;

for (; index < arr.length; index++, i++) {

queue.add(arr[index]);

arr[i] = queue.poll();

}

while (!queue.isEmpty()) {

arr[i++] = queue.poll();

}

public static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int K) {

int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

for (int i = 0; i < arr.length; i++) {

arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());

}

// 先排个序

Arrays.sort(arr);

// 然后开始随意交换，但是保证每个数距离不超过K

// swap[i] == true, 表示i位置已经参与过交换

// swap[i] == false, 表示i位置没有参与过交换

boolean[] isSwap = new boolean[arr.length];

for (int i = 0; i < arr.length; i++) {

int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);

if (!isSwap[i] && !isSwap[j]) {

isSwap[i] = true;

isSwap[j] = true;

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

return arr;

}

public static void main(String[] args) {

System.out.println("test begin");

int testTime = 500000;

int maxSize = 100;

int maxValue = 100;

boolean succeed = true;

for (int i = 0; i < testTime; i++) {

int k = (int) (Math.random() * maxSize) + 1;

int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);

int[] copiedOf1 = Arrays.copyOf(arr, arr.length);

int[] copiedOf2 = Arrays.copyOf(arr, arr.length);

sortedArrDistanceLessK(copiedOf1, k);

Arrays.sort(copiedOf2);

if (!Arrays.equals(copiedOf1, copiedOf2)) {

succeed = false;

System.out.println("K : " + k);

System.out.println("arr : " + Arrays.toString(arr));

System.out.println("copiedOf1 : " + Arrays.toString(copiedOf1));

System.out.println("copiedOf2 : " + Arrays.toString(copiedOf2));

break;

}

System.out.println(succeed ? "Nice!" : "Fucking fucked!");

}

题目二

合并k个已排序的链表

合并k个已排序的链表_牛客题霸_牛客网

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤5000，每个节点的val满足 ∣val∣<=1000

要求：时间复杂度 O(nlogn)

示例1

输入：[{1,2,3},{4,5,6,7}]

返回值：{1,2,3,4,5,6,7}

5.2.1 思路

将每个链表的头节点压入小根堆，然后弹出的第一个元素是需要返回的元素，然后判断弹出元素是否有下个元素，如果有再压入小根堆然后直到小根堆中的值全部弹出。

5.2.2 代码

public ListNode mergeKLists(ArrayList<ListNode> lists) {

// write code here

PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

for (ListNode list : lists) {

if (list != null) {

heap.add(list);

}

if (heap.isEmpty()) {

return null;

}

ListNode ans = heap.poll();

ListNode cur = ans;

if (cur.next != null) {

heap.add(cur.next);

}

while (!heap.isEmpty()) {

ListNode next = heap.poll();

cur.next = next;

cur = next;

if (next.next != null) {

heap.add(next.next);

}

return ans;

}

// 只提交mergeKLists这个方法即可

public static class ListNode {

int val;

ListNode next = null;

public ListNode(int val) {

this.val = val;

}

题目三

牛客链接测试：线段重合_牛客题霸_牛客网

给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间

规定：

线段的开始和结束位置一定都是整数值
线段重合区域的长度必须>0

返回线段最多重合区域中，包含了几条线段

思路一

使用一个比较笨的办法，我们先将数组排序求出一个最大值 max 和一个最小值 min,这样就能确定数据是从 min开始 max结束。那么我们求 min + 0.5也就是求 min 到 max 之间每个数加 0.5 有多少个线段在这个数中，最后求出最大值即可。时间复杂度为 O((max-min)*N)

代码

public static int getMaxConvert01(int[][] segments) {

if (segments == null || segments.length == 0) {

return 0;

}

int min = Integer.MAX_VALUE;

int max = Integer.MIN_VALUE;

for (int[] segment : segments) {

min = Math.min(min, segment[0]);

max = Math.max(max, segment[1]);

}

int ans = 0;

for (double i = min + 0.5; i < max; i++) {

int cur = 0;

for (int[] segment : segments) {

if (segment[0] < i && segment[1] > i) {

cur++;

}

ans = Math.max(ans, cur);

}

return ans;

}

思路二

使用堆排序，我们可以将数组的开始位置进行排序，然后依次枚举数组的开始位置具体操作如下

建立一个小根堆，用于存放线段的结束位置
依次枚举线段，将小根堆中的数小于线段开始位置的数弹出，然后压入线段的结束，计算小根堆中的数的数量
依次比较求最大值

时间复杂度为 O(N*logN)

代码

public static int getMaxConvert02(int[][] segments) {

if (segments == null || segments.length == 0) {

return 0;

}

Arrays.sort(segments, Comparator.comparingInt(o -> o[0]));

PriorityQueue<Integer> heap = new PriorityQueue<>();

int ans = 0;

for (int[] segment : segments) {

while (!heap.isEmpty() && heap.peek() <= segment[0]) {

heap.poll();

}

heap.add(segment[1]);

ans = Math.max(ans, heap.size());

}

return ans;

}

完整代码以及对数器

import java.util.Arrays;

import java.util.Comparator;

import java.util.PriorityQueue;

/**

* 最大线段重合问题

* 给定很多线段，每个线段都有两个数[start, end]，

* 表示线段开始位置和结束位置，左右都是闭区间

* 规定：

* 1）线段的开始和结束位置一定都是整数值

* 2）线段重合区域的长度必须 >0

* 返回线段最多重合区域中，包含了几条线段

public class Code01_ConvertMax {

public static int getMaxConvert01(int[][] segments) {

if (segments == null || segments.length == 0) {

return 0;

}

int min = Integer.MAX_VALUE;

int max = Integer.MIN_VALUE;

for (int[] segment : segments) {

min = Math.min(min, segment[0]);

max = Math.max(max, segment[1]);

}

int ans = 0;

for (double i = min + 0.5; i < max; i++) {

int cur = 0;

for (int[] segment : segments) {

if (segment[0] < i && segment[1] > i) {

cur++;

}

ans = Math.max(ans, cur);

}

return ans;

}

public static int getMaxConvert02(int[][] segments) {

if (segments == null || segments.length == 0) {

return 0;

}

Arrays.sort(segments, Comparator.comparingInt(o -> o[0]));

PriorityQueue<Integer> heap = new PriorityQueue<>();

int ans = 0;

for (int[] segment : segments) {

while (!heap.isEmpty() && heap.peek() <= segment[0]) {

heap.poll();

}

heap.add(segment[1]);

ans = Math.max(ans, heap.size());

}

return ans;

}

public static int[][] generateLines(int N, int L, int R) {

int size = (int) (Math.random() * N) + 1;

int[][] ans = new int[size][2];

for (int i = 0; i < size; i++) {

int a = L + (int) (Math.random() * (R - L + 1));

int b = L + (int) (Math.random() * (R - L + 1));

if (a == b) {

b = a + 1;

}

ans[i][0] = Math.min(a, b);

ans[i][1] = Math.max(a, b);

}

return ans;

}

public static void main(String[] args) {

System.out.println("test begin");

int N = 100;

int L = 0;

int R = 200;

int testTimes = 200000;

for (int i = 0; i < testTimes; i++) {

int[][] lines = generateLines(N, L, R);

int ans1 = getMaxConvert01(lines);

int ans2 = getMaxConvert02(lines);

if (ans1 != ans2) {

System.out.println("Oops!");

}

System.out.println("test end");

}

牛客提交代码

import java.util.Scanner;

import java.io.*;

import java.util.Arrays;

import java.util.Comparator;

import java.util.PriorityQueue;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

private static Integer MAX = 10001;

private static int[][] line = new int[MAX][2];

private static int n;

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StreamTokenizer in = new StreamTokenizer(br);

PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

while (in.nextToken()!=StreamTokenizer.TT_EOF){

n = (int)in.nval;

for (int i = 0; i < n; i++) {

in.nextToken();

line[i][0] = (int)in.nval;

in.nextToken();

line[i][1] = (int)in.nval;

}

out.println(getMaxConvert());

out.flush();

br.close();

}

public static int getMaxConvert() {

if (line == null || line.length == 0) {

return 0;

}

Arrays.sort(line, Comparator.comparingInt(o -> o[0]));

PriorityQueue<Integer> heap = new PriorityQueue<>();

int ans = 0;

for (int[] segment : line) {

while (!heap.isEmpty() && heap.peek() <= segment[0]) {

heap.poll();

}

heap.add(segment[1]);

ans = Math.max(ans, heap.size());

}

return ans;

}

题目四

leetCode2208

https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/

5.4.1 实现思路

题目要求是求出数组总和 sum，然后每次取一个数的一半累计和 ansSum要求是求 ansSum需要加多少次才能到达 sum的一半。如果说每次都取数组中的最大值，然后取一半的值加起来求出次数就是答案

使用大根堆，每次弹出最大值，然后取一半再放进去直到达到 ansSum>=sum 位置一共加了多少次即可

5.4.2 实现代码

public int halveArray(int[] nums) {

if (nums == null || nums.length == 0) {

return 0;

}

PriorityQueue<Double> heap = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));

double sum = 0;

for (int num : nums) {

sum += num;

heap.add((double) num);

}

sum/=2;

int count = 0;

double curSum = 0;

while (curSum < sum && !heap.isEmpty()) {

double poll = heap.poll() / 2;

curSum += poll;

heap.add(poll);

count++;

}

return count;

}

5.4.3 手动实现堆代码

// 手动实现一个堆结构

public static int MAX = 100001;

public static long[] heap = new long[MAX];

public static int size;

public static int halveArray(int[] nums) {

size = nums.length;

long sum = 0;

for (int i = size - 1; i >= 0; i--) {

heap[i] = (long) nums[i] << 20;

sum += heap[i];

heapify(i);

}

sum/=2;

int count = 0;

double curSum = 0;

while (curSum < sum ) {

heap[0] /= 2;

curSum += heap[0];

count++;

heapify(0);

}

return count;

}

public static void heapify(int index) {

int left = (index << 1) + 1;

while (left < size) {

int largest = left + 1 < size && heap[left + 1] > heap[left] ? left + 1 : left;

largest = heap[largest] > heap[index] ? largest : index;

if (largest == index) {

break;

}

swap(largest, index);

index = largest;

left = (index << 1) + 1;

}

public static void swap(int i, int j) {

long tmp = heap[i];

heap[i] = heap[j];

heap[j] = tmp;

}

二、堆的实现、

2.1 堆的向上调整算法

2.1.1 思路

堆的向下调整算法

2.2.1 思路

2.3 堆结构完整代码

三、堆排序

3.1 思路

3.2 代码

四、堆排序的时间复杂度

五、面试题

5.1 题目一

5.1.1 思路

5.1.2 代码

题目二

描述

示例1

5.2.1 思路

5.2.2 代码

题目三

思路一

代码

思路二

代码

完整代码以及对数器

牛客提交代码

题目四

5.4.1 实现思路

5.4.2 实现代码

5.4.3 手动实现堆 代码

5.4.3 手动实现堆代码

数据结构和算法 - 堆和堆排序的全部评论