编程导航会员会员
登录/注册

数据结构和算法 - 堆和堆排序

一、堆结构的定义


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

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

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




二、堆的实现、


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 思路


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




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]，表示线段开始位置和结束位置，左右都是闭区间

规定：

  1. 线段的开始和结束位置一定都是整数值
  2. 线段重合区域的长度必须>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;
}


思路二


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

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

时间复杂度为 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;
}







数据结构
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
若谷
若谷
等级vip
内容推荐
更多
个人觉得不错的数据结构和算法课程#资源# 资源#链接: https://pan.baidu.com/s/1Q_Qo8l7Xhonf1RaSDpMqaw?pwd=n3vi 提取码: n3vi--来自百度网盘超级会员v4的分享
19
考研 #数据结构#字符串匹配，暴击匹配，主要涉及到指针回退，i=i-j 2和j=1，然后就是指针的后移，字符挨个比对KMP算法，第一遍，听不懂，只理解了一点next数组，其他的是啥也听不懂啊
11
3 月 28 打卡，学习手搓环形数组
2
一文带你学会"冒泡排序"
6
Go 语言中的数组、切片、Map和List
2
作者分享
更多
AI超级智能体 - 一、接入AI大模型
9
亿级流量点赞系统-最终篇
5
亿级流量点赞系统-第十章
4
亿级流量点赞系统-第九章
6
亿级流量点赞系统-第八章
5
下载 APP