参考：漫画：什么是二叉堆？
- 大根堆
- 小根堆
参考：漫画：什么是堆排序？
参考：漫画：什么是优先队列？
参考：【video】视频--第14周10--第8章排序10--8.4选择排序3--堆排序2--堆调整
堆的调整（小根堆）
- 输出堆顶元素之后，以堆中最后一个元素替代之；
- 然后将根节点值与左、右子树的根节点值进行比较，并与其中小者进行交换；
- 重复上述操作，直至叶子节点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
大根堆与上面类似。
通过3中方法实现ADT：
- 堆的形式
- 无序array
- 有序array
第一步：一组数据
如下图：
第二步：构建完全二叉树
第三步：构建大根堆
从 last_child/2 节点往前，每个节点与其子节点比较，按照 fixDown 操作，如下图：
第四步：pop 最大值
执行 delMax 操作，将最大值输出，然后将最后的节点编程根节点，然后执行 fixDown 操作，如下图：
参考：HEAP SORT
代码实现如下：
pq.h
// pq.h: ADT interface for a priority queue #include <stdio.h> #include <stdlib.h> typedef struct pqRep *PQ; PQ createPQ(int size); void insertPQ(PQ q, int it); int delMaxPQ(PQ q); int isEmptyPQ(PQ q);
pqSort.c
/* pqSort.c: use a priority queue to sort an array of integers
into descending order
*/
#include "pq.h"
int main() {
int a[] = {41, 2, 58, 156, 360, 81, 260, 74, 167, 13};
int length = sizeof(a)/sizeof(a[0]);
PQ q = createPQ(length);
printf("Array: ");
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
insertPQ(q, a[i]);
}
printf("
Sorted: ");
while (!isEmptyPQ(q)) {
printf("%d ", delMaxPQ(q));
}
putchar('
');
return EXIT_SUCCESS;
}
pqHP.c
// pqHP.c: priority queue implementation for pq.h using a heap
#include "pq.h"
// 'static' means these functions are for local use only
static void fixDown(int *, int, int);
static void fixUp(int *, int);
// Priority queue implementation using an unordered array
struct pqRep {
int nItems; // actual count of Items
int *items; // array of Items
int maxsize; // maximum size of array
};
PQ createPQ(int size) {
PQ q = malloc(sizeof(struct pqRep)); // make room for the structure
if (q == NULL) {
fprintf(stderr, "out of memory
");
exit(0);
}
q->items = malloc((size+1) * sizeof(int)); // make room for the array
if (q->items == NULL) { // size+1 because heap 1..size
fprintf(stderr, "out of memory
");
exit(0);
}
q->nItems = 0; // we have no items yet
q->maxsize = size; // remember the maxsize
return q; // return the initial PQ
}
void insertPQ(PQ q, int it) {
if (q == NULL) {
fprintf(stderr, "priority queue not initialised
");
exit(1);
}
if (q->nItems == q->maxsize) {
fprintf(stderr, "priority queue full
");
exit(1);
}
q->nItems++; // adding another item
q->items[q->nItems] = it; // put the item at the end
fixUp(q->items, q->nItems); // fixUp all the way to the root
return;
}
int delMaxPQ(PQ q) {
if (q == NULL) {
fprintf(stderr, "priority queue not initialised
");
exit(1);
}
if (q->nItems == 0) {
fprintf(stderr, "priority queue empty
");
exit(1);
}
int retval = q->items[1]; // this is the item we want to return
q->items[1] = q->items[q->nItems]; // overwrite root by last item
q->nItems--; // we are decreasing heap size by 1
fixDown(q->items, 1, q->nItems); // fixDown the new root
return retval;
}
int isEmptyPQ(PQ q) {
int empty = 0;
if (q == NULL) {
fprintf(stderr, "isEmptyPQ: priority queue not initialised
");
}
else {
empty = q->nItems == 0;
}
return empty;
}
// fix up the heap for the 'new' element child
void fixUp(int *heap, int child) {
while (child>1 && heap[child/2]<heap[child]) {
int swap = heap[child]; // if parent < child, do a swap
heap[child] = heap[child/2];
heap[child/2] = swap;
child = child/2; // become the parent
}
return;
}
// force value at a[par] into correct position
void fixDown(int *heap, int par, int len) {
int finished = 0;
while (2*par<=len && !finished) {// as long as you are within bounds
int child = 2*par; // the first child is here
if (child<len && heap[child]<heap[child+1]) {
child++; // choose larger of two children
}
if (heap[par]<heap[child]) { // if node is smaller than this child ...
int swap = heap[child]; // if parent < child, do a swap
heap[child] = heap[child/2];
heap[child/2] = swap;
par = child; // ... and become this child
}
else {
finished = 1; // else we do not have to go any further
}
}
return;
}
Compile and run:
prompt$ dcc pqHP.c pqSort.c prompt$ ./a.out Array: 41 2 58 156 360 81 260 74 167 13 Sorted: 360 260 167 156 81 74 58 41 13 2
通过array来实现ADT，就是每次通过遍历比array里面的最大值，然后输出，并由最后一个元素补位
pqUA.c
// pqUA.c: priority queue implementation for pq.h using an unordered array
#include "pq.h"
struct pqRep {
int nItems; // actual count of Items
int *items; // array of Items
int maxsize; // maximum size of array
};
PQ createPQ(int size) {
PQ q = malloc(sizeof(struct pqRep)); // make room for the structure
if (q == NULL) {
fprintf(stderr, "out of memory
");
exit(0);
}
q->items = malloc(size * sizeof(int)); // make room for the array
if (q->items == NULL) {
fprintf(stderr, "out of memory
");
exit(0);
}
q->nItems = 0; // we have no items yet
q->maxsize = size; // remember the maxsize
return q; // return the initial PQ
}
void insertPQ(PQ q, int it) {
if (q == NULL) {
fprintf(stderr, "priority queue not initialised
");
exit(1);
}
if (q->nItems == q->maxsize) {
fprintf(stderr, "priority queue full
");
exit(1);
}
q->items[q->nItems] = it; // UNORDERED ARRAY, so put item at the end
q->nItems++; // increment the 'counter'
}
int delMaxPQ(PQ q) { // UNORDERED, so need to linear search for max item
if (q == NULL) {
fprintf(stderr, "delmaxPQ: priority queue not initialised
");
exit(1);
}
if (q->nItems == 0) {
fprintf(stderr, "priority queue empty
");
exit(1);
}
int *array = q->items;
int last = q->nItems-1; // items occupy places 0 .. last
int max = 0; // assume initially item at max=0 has largest key
for (int i = 1; i <= last; i++){
if (array[max] < array[i]){ // now compare with every other item
max = i; // whenever we find a better one, update max
}
}
int retval = array[max]; // save the max item
array[max] = array[last]; // overwrite max location with last item
q->nItems--; // decrease the number of items
return retval; // return the max element
}
int isEmptyPQ(PQ q) {
int empty = 0;
if (q == NULL) {
fprintf(stderr, "isEmptyPQ: priority queue not initialised
");
}
else {
empty = q->nItems == 0;
}
return empty;
}
也可以通过有序array来实现，就是在插入的过程中就进行排序
pqOA.c
// pqOA.c: priority queue implementation for pq.h using an ordered array
#include "pq.h"
struct pqRep {
int nItems; // actual count of Items
int *items; // array of Items
int maxsize; // maximum size of array
};
PQ createPQ(int size) {
PQ q = malloc(sizeof(struct pqRep)); // make room for the structure
if (q == NULL) {
fprintf(stderr, "out of memory
");
exit(0);
}
q->items = malloc(size * sizeof(int)); // make room for the array
if (q->items == NULL) {
fprintf(stderr, "out of memory
");
exit(0);
}
q->nItems = 0; // we have no items yet
q->maxsize = size; // remember the maxsize
return q; // return the initial PQ
}
void insertPQ(PQ q, int it) {
if (q == NULL) {
fprintf(stderr, "priority queue not initialised
");
exit(1);
}
if (q->nItems == q->maxsize) {
fprintf(stderr, "priority queue full
");
exit(1);
}
int *array = q->items;
int last = q->nItems;
int i;
for (i=0; i<last && array[i]<it; i++) {
; // find location of item == it
}
int j;
for (j = last; j>i; j--){ // starting at last and go down to i
array[j] = array[j-1]; // shift items up
}
array[i] = it; // now insert item 'it' at i
q->nItems++; // increase the count
}
int delMaxPQ(PQ q) {
if (q == NULL) {
fprintf(stderr, "priority queue not initialised
");
exit(1);
}
if (q->nItems == 0) {
fprintf(stderr, "priority queue empty
");
exit(1);
}
q->nItems--;
return q->items[q->nItems];
}
int isEmptyPQ(PQ q) {
int empty = 0;
if (q == NULL) {
fprintf(stderr, "isEmptyPQ: priority queue not initialised
");
}
else {
empty = q->nItems == 0;
}
return empty;
}