# 纸上谈兵: 堆 (heap)

+关注继续查看

Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程，每个进程有不同的优先级(该优先级的计算会综合多个因素，比如进程所需要耗费的时间，进程已经等待的时间，用户的优先级，用户设定的进程优先程度等等)。内核会找到优先级最高的进程，并执行。如果有优先级更高的进程被提交，那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。

(Linux中可以使用nice命令来影响进程的优先级)

### 堆的实现

/* By Vamei
Use an big array to implement heap
DECLARE: int heap[MAXSIZE] in calling function
heap[0] : total nodes in the heap
for a node i, its children are i*2 and i*2+1 (if exists)
its parent is i/2  */

void insert(int new, int heap[])
{
int childIdx, parentIdx;
heap[0] = heap[0] + 1;
heap[heap[0]] = new;

/* recover heap property */
percolate_up(heap);
}

static void percolate_up(int heap[]) {
int lightIdx, parentIdx;
lightIdx  = heap[0];
parentIdx = lightIdx/2;
/* lightIdx is root? && swap? */
while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
/* swap */
swap(heap + lightIdx, heap + parentIdx);
lightIdx  = parentIdx;
parentIdx = lightIdx/2;
}
}

int delete_min(int heap[])
{
int min;
if (heap[0] < 1) {
/* delete element from an empty heap */
printf("Error: delete_min from an empty heap.");
exit(1);
}

/* delete root
move the last leaf to the root */
min = heap[1];
swap(heap + 1, heap + heap[0]);
heap[0] -= 1;

/* recover heap property */
percolate_down(heap);

return min;
}

static void percolate_down(int heap[]) {
int heavyIdx;
int childIdx1, childIdx2, minIdx;
int sign; /* state variable, 1: swap; 0: no swap */

heavyIdx = 1;
do {
sign     = 0;
childIdx1 = heavyIdx*2;
childIdx2 = childIdx1 + 1;
if (childIdx1 > heap[0]) {
/* both children are null */
break;
}
else if (childIdx2 > heap[0]) {
/* right children is null */
minIdx = childIdx1;
}
else {
minIdx = (heap[childIdx1] < heap[childIdx2]) ?
childIdx1 : childIdx2;
}

if (heap[heavyIdx] > heap[minIdx]) {
/* swap with child */
swap(heap + heavyIdx, heap + minIdx);
heavyIdx = minIdx;
sign = 1;
}
} while(sign == 1);
}

### 总结

【数据结构】堆（万字详解）
【数据结构】堆（万字详解）
19 0

20 0

7 0
【数据结构】堆（一）——堆的实现（二）
【数据结构】堆（一）——堆的实现（二）
18 0
【数据结构】堆（一）——堆的实现（一）
【数据结构】堆（一）——堆的实现（一）
35 0
08-堆（一）
08-堆（一）
15 0
08-堆（三）
08-堆（三）
25 0
JVM系列（八）：堆（Heap）的相关知识介绍

60 0

44 0

58 0
+关注
vamei