Ajustup函数：
二叉树的性质：child=2*parent+1
(可参考我的另外一篇博客：http://t.csdn.cn/GLlHN)
如果child<parent时，child和parent交换，交换后child=parent。否则break跳出循环。以此循环，当child来到根节点时结束，即：下标为0。
void Ajustup(HPDataType*a, int child) {//N*logN assert(a); //int child = n - 1; while (child > 0) { int parent = (child - 1) / 2; if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; } else { break; } } }
交换可以写一个函数Swap来复用，会用到很多次。
void Swap(HPDataType* p1, HPDataType* p2) { assert(p1); assert(p2); HPDataType tmp = 0; tmp = *p1; *p1 = *p2; *p2 = tmp; }
HeapPop函数：
出数据只能是出堆顶的元素（根节点），否则没有什么意义。
当我们将根节点删除后，它的左子节点leftchild和右子节点rightchild谁来当根节点呢？ 并且我们还得维持它是一个堆，也就是维持它是一个完全二叉树。
假设左子节点大于右子节点时，让左子节点当根节点会出现什么情况呢？
显然这种方法是不可行的！！！
换一种思路：
让第一个位置的值和最后一个位置的值，再size--不就相当于删除了嘛，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。
void HeapPop(HP* php) { assert(php); assert(php->size > 0); Swap(&php->a[0], &php->a[php->size-1]); php->size--; Ajustdown(php->a, php->size-1 , 0); }
Ajustdown函数：
- 由性质child=2*parent+1，反推：parent=（child-1）/2。
假设左子节点大，左子节点leftchild大于右子节点rightchild ，当左子节点小于右子节点，child++找到子节点大的那一个。
当parent>child时交换，parent=child、child=2*child+1。
void Ajustdown(HPDataType* a, int n,int parent) {//O(N) assert(a); int child = 2 * parent+1; while (child<n) { if (child + 1 < n && a[child] < a[child + 1])// <假设左子树大 { child++; } if (a[child] > a[parent])//>大堆，<为小堆 { Swap(&a[child], &a[parent]); parent = child; child = child * 2 + 1; } else { break; } } }
HeapTop、HeapSize、HeapEmpty函数较为直接，就不做解释了。
HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; } int HeapSize(HP* php) { assert(php); return php->size; } bool HeapEmpty(HP* php) { assert(php); if (php->size == 0) return true; else return false; }
代码实现：
Heap.h文件：
#define _CRT_SECURE_NO_WARNINGS #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #include<string.h> #include<time.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void Swap(HPDataType* p1, HPDataType* p2); void HeapCreate(HP* php, HPDataType* a, int n); void HeapPrintf(HP* php); void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); int HeapSize(HP* hp); bool HeapEmpty(HP* hp); void Ajustdown(HPDataType* a, int n, int parent); void Ajustup(HPDataType* a, int n);
Heap.c文件:
#include"Heap.h" void HeapInit(HP* php) { assert(php); php->capacity = 0; php->size = 0; php->a = NULL; } void HeapDestroy(HP* php) { assert(php); assert(php->a); free(php->a); free(php); } void HeapPrintf(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); } void Swap(HPDataType* p1, HPDataType* p2) { assert(p1); assert(p2); HPDataType tmp = 0; tmp = *p1; *p1 = *p2; *p2 = tmp; } void Ajustup(HPDataType*a, int child) {//N*logN assert(a); //int child = n - 1; while (child > 0) { int parent = (child - 1) / 2; if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; } else { break; } } } void Ajustdown(HPDataType* a, int n,int parent) {//O(N) assert(a); int child = 2 * parent+1; while (child<n) { if (child + 1 < n && a[child] < a[child + 1])// <假设左子树大 { child++; } if (a[child] > a[parent])//>大堆，<为小堆 { Swap(&a[child], &a[parent]); parent = child; child = child * 2 + 1; } else { break; } } } void HeapCreate(HP* php, HPDataType* a, int n) { assert(php); HPDataType*tmp=(HPDataType*)malloc(sizeof(HPDataType) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } memcpy(php->a, tmp, sizeof(HPDataType)*n); php->size = php->capacity = n; for (int i = (n - 1 - 1) / 2; i >= 0; i--) { Ajustdown(php->a, n, i); } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->size == php->capacity) { int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->size++] = x; Ajustup(php->a, php->size-1); } void HeapPop(HP* php) { assert(php); assert(php->size > 0); Swap(&php->a[0], &php->a[php->size-1]); php->size--; Ajustdown(php->a, php->size-1 , 0); } HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; } int HeapSize(HP* php) { assert(php); return php->size; } bool HeapEmpty(HP* php) { assert(php); if (php->size == 0) return true; else return false; }
Test.c文件：
#include"Heap.h" void test1() { HP php; HeapInit(&php); HeapPush(&php, 75); HeapPush(&php, 56); HeapPush(&php, 30); HeapPush(&php, 25); //HeapPop(&php); int a=HeapSize(&php); printf("%d\n", a); HeapPrintf(&php); HeapPush(&php, 100); HeapPrintf(&php); HeapPop(&php); HeapPrintf(&php); HeapDestroy(&php); } int main() { test1(); //test2(); //test3(); //test4(); return 0; }
