- 二叉堆基本操作
- 使用数组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];
}
思路2:
二叉堆基本操作：
float :依次与parent node 比较，交换
sink：一次与left node/ parent node 比较，递归sink
insert: 依次插入节点到最后，float 新插入的节点
pop： pop root 节点，swap root 和最后一个节点， sink;
findKthLargest:
构建N Max- heap；
pop K次，获取Kth 大
struct heapStruct {
int *arr;
int capacity;
int size;
};
#define LEFT(i) ((i)*2+1)
#define RIGHT(i) ((i)*2+2)
#define PARENT(i) ((i-1)/2)
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void floatHeap(struct heapStruct *heap, int i)
{
int curIndex = i;
int parentIndex = PARENT(curIndex);
while(curIndex && heap->arr[curIndex] > heap->arr[parentIndex]) {
swap(&heap->arr[curIndex], &heap->arr[parentIndex]);
curIndex = parentIndex;
parentIndex = (curIndex - 1)/2;
}
}
void sinkHeap(struct heapStruct *heap, int i)
{
int largest = i;
int left = LEFT(i);
int right = RIGHT(i);
if (left < heap->size && heap->arr[left] > heap->arr[largest])
largest = left;
if (right < heap->size && heap->arr[right] > heap->arr[largest])
largest = right;
if (largest != i) {
swap(&heap->arr[i], &heap->arr[largest]);
sinkHeap(heap, largest);
}
}
void insertHeap(struct heapStruct *heap, int value)
{
heap->arr[heap->size] = value;
heap->size++;
floatHeap(heap, heap->size-1);
}
struct heapStruct *buildHeap(int *num, int numsSize)
{
struct heapStruct *heap = (struct heapStruct *)malloc(sizeof(struct heapStruct));
heap->arr = malloc(sizeof(int) * numsSize);
heap->size = 0;
heap->capacity = numsSize;
int i;
for(i=0;i<numsSize;i++) {
insertHeap(heap,num[i]);
}
return heap;
}
int findKthLargest(int* nums, int numsSize, int k){
struct heapStruct *heap = buildHeap(nums, numsSize);
int i;
int max;
for(i=0;i<k;i++) {
//1. pop max = heap->arr[0];
max = heap->arr[0];
//2. swap(0, heap->size-1);
swap(&heap->arr[0], &heap->arr[heap->size-1]);
heap->size--;
//3. sinkHeap
sinkHeap(heap, 0);
printf("%dth %d\n",i, max);
}
return max;
}
类似的问题：
数组最小的K个数，
TopK(TopK 高频单词，高频元素，最近的点）
字符出现频率排序
数据流中最大的第K 个数
数据流中位数
