堆和优先队列

一、大顶堆和小顶堆

大顶堆： 每一个结点：（当前结点> max (左结点、右结点）小顶堆： 每一个结点：（当前结点 < min (左结点、右结点）

由定义的出来，大顶堆的最大值一定是在跟结点，次最大值是在第二层，其余的大小不能判定； 同理可以得到，小顶堆的最小值一定是在跟结点。

二、大顶堆的相关操作

定义 typedef struct heap { int *data; int size; int cnt; } heap;

data用于存放连续区域的数字， size表示最多能存放的数字 cnt表示当前存放了多少数字

void init(heap *p, int size) { p->data = (int *)malloc(sizeof(int)*size); p->cnt = 1; p->size = size; }

初始化函数，

push 操作 int push(heap *q, int value) { if (q == NULL) return 0; if (q->cnt == q->size) return 0; q->data[++(q->cnt)] = val; int ind = q->cnt; while(int >> 1 && q->data[ind] > q->data[ind >> 1]) { swap(q->data[ind], q->data[ind >> 1]); ind >>= 1; } }

在加入一个新的元素value之后，我需要保证大顶堆还是正确的，为了保证这一点，我需要拿value往父亲结点比较，如果我发现父亲结点的值比value小，那么我就需要交换两值。

我要重复这个操作，直到发现当前结点的值是小于父亲结点的。 在这个期间我需要保证，ind的值不断的缩小，靠近跟结点，到ind是零，这个也就改结束了。

pop

首先，pop是把跟结点探出去，然后用最后一个结点的值赋给跟结点。 我们知道跟结点应该是最大的值，我们不如就把根结点就放到最后一个结点的位置上，这样就保留了每一次pop的最大值。

其次，pop结束后，我必须从跟结点出发（ind == 1)观察左右孩子结点是否大于当前结点 如果都大于，我应该让当前结点与左右结点中最大的那个数交换 如果左右其中之一大于，我也应该交换

int pop(head *p) { if (q == NULL) return 0; if (q->cnt == 0) return 0; q->data[1] = q->data[q->cnt--]; int ind = 1; while ((ind << 1) <= q->cnt) { int temp = ind, l = ind << 1, r = ind << 1 | 1; if(q->data[l] > q->data[temp]) temp = l; if(q->data[r] > q->data[temp]) temp = r; if(temp == ind) break; swap(q->data[temp], q->data[index]); } return 1; }

经过上述操作，temp是l、r中间对应到data的比较大的值，我们需要交换。 如果发现l、r中没有比当前结点大的数，那就说明这个操作已经结束了。

三、其他方式实现pop

void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }

此时swap函数可以如上写。 pop函数如下： 我目前的h-data和最后一个元素交换，那头就是最小的元素了，我就需要把这个堆更新一下， 更新范围比pop之前的size少一个就好了。

void pop(Head *p) { swap(&h->data[0], &h->data[h->size - 1]); h->size--; update(h, 0, h->size); }

update: 如果两个孩子中，有比当前的大的数，那么就要交换；到什么时候结束呢？到我目前的数到了找不到比他大结束

void update(Heap *h, int pos, int n) { int lchild = pos * 2; while (lchild < n) { int rchild = pos * 2 + 1; int temp = pos; if(h->data[lchild] < h->data[pos]) temp = lchild; if(h->data[rchild] < h->data[pos]) temp = rchild; if(temp == pos) break;//结束了 swap(&h->data[pos], &h->data[temp]); pos = temp; lchild *= 2; } return ; }

堆排序函数 heap_sort： 1. h->size - 1， 从 2.

void heap_sort(Heap *h) { for (int i = h->size - 1; i >= 1; i--) { swap(&h->data[i], &h->data[0]); update(h, 0, i); } }

当循环到1退出，为什么是循环到0呢？ 因为循环到第0个元素的时候，就是元素自己和自己交换，所以第0个元素可以不用自己处理.

首先是将当前的元素data[i]和堆顶的元素 n

四、排序方法

downUpdate(int *arr, int n, int ind)

表示ind,最根本的结点，ind 变成原来的两倍，如果这种情况下，是小于最大值n的，那么我们就

对它往下进行更新

void downUpdate(int *arr, int n, int ind) { while((ind << 1) <= n) { int temp = ind, l = ind << 1, r = ind << 1 | 1; if (arr[l] > arr[temp]) temp = l; if (r <= n && arr[r] > arr[temp]) temp = r; if (temp = ind) break; swap(arr[temp], arr[ind]); ind = temp; } return ; }