- 二叉堆基本操作
- 使用数组A[1...n]，可近视看作一个完全二叉树。
- 树中每个node 对应数组的一个元素
-
树的每一层（除了最后一层尽可能）都从左到右依次填满；
image.png
- 每个节点的父子节点的索引
/*
* 数组从索引从1开始
*/
PARENT(i)
return i/2;
LEFT(i)
return 2i;
RIGHT(i)
return 2i+1;
/*
* 数组从索引从0开始
*/
PARENT(i)
return (i-1)/2;
LEFT(i)
return 2i+1;
RIGHT(i)
return 2i+2;
- 堆的属性
(1)最大堆
A[PARENT(i)] >= A[i]
(2) 最小堆
A[PARENT(i)] <= A[i]
-
下沉操作
image.png
-
构建堆
image.png
-
堆排序
image.png
二叉堆应用-leetcode-数组第K大数-源码C实现
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
//基本数据结构
struct MinHeap {
int *arr;
int size;
int capacity;
};
//获取节点的parent，left child, right chid 索引
#define PARENT(i) ((i - 1)/2)
#define LEFT_CHILD(i) (2 * (i) + 1)
#define RIGHT_CHILD(i) (2 * (i) + 2)
//基本操作：交换
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
//初始化，分配数组
void minhead_init(struct MinHeap *heap, int cap){
heap->capacity = cap;
heap->arr = malloc(sizeof(int) * heap->capacity);
heap->size = 0;
}
/*
/*
swim 上浮基本操作就是
（1）与父节点比较，
（2）交换
（3）准备下一次循环
*/
void minheap_swim(struct MinHeap *heap, int index) {
int parent = PARENT(index);
while(index>0 && heap->arr[index] < heap->arr[parent]) {
swap(&heap->arr[index], &heap->arr[parent]);
index = parent;
parent = PARENT(index);
}
}
/*
sink 下沉基本操作：
1. 与left child, right child 比较
2. 与最大的child 交换
3. 递归sink 最大child 所在子树
*/
void minheap_sink(struct MinHeap *heap, int index) {
int leftchild = LEFT_CHILD(index);
int rightchild = RIGHT_CHILD(index);
int smallest = index;
if(leftchild < heap->capacity && heap->arr[smallest] > heap->arr[leftchild]) {
smallest = leftchild;
}
if(rightchild < heap->capacity && heap->arr[smallest] > heap->arr[rightchild]) {
smallest = rightchild;
}
if (index != smallest) {
swap(&heap->arr[smallest], &heap->arr[index]);
minheap_sink(heap, smallest);
}
}
/* heap 固定大小 的堆
* 1.固定大小堆
* （1） 增加堆size, 上浮操作
* （2） 不增加size, 放堆顶，下沉操作
*
* 2.基本思想：
* （1） 小于容量，则逐个push 到堆中，然后对这个位置进行上浮处理
* （2）当达到heap容量，当且只有新值大于最小堆的堆顶值时，才
* 处理：（1）放到堆顶（2）对堆顶进行下沉操作
*/
void minheap_insert(struct MinHeap *heap, int val) {
if (heap->size < heap->capacity) {
heap->arr[heap->size++] = val;//直接放数组最后
minheap_swim(heap, heap->size - 1);//最后一个元素，处理，上浮
} else if (val > heap->arr[0]) {// 堆满，且值大于最小值，
heap->arr[0] = val;
minheap_sink(heap, 0);
}
}
int findKthLargest(int* nums, int numsSize, int k){
struct MinHeap minheap;
minhead_init(&minheap, k);
int i;
for (i=0;i<numsSize;i++) {
minheap_insert(&minheap, nums[i]);
}
return minheap.arr[0];
}
类似的问题：
数组最小的K个数，
TopK(TopK 高频单词，高频元素，最近的点）
字符出现频率排序
数据流中最大的第K 个数
数据流中位数
网友评论