//删除最小元素,在小顶堆即意味着删除根节点 intdeleteMin(heap* h) { int child; int result = h->data[1]; h->data[1] = h->data[h->size]; h->size--; int i = 1; int temp = h->data[1]; for (i = 1; 2 * i <= h->size; i = child) { child = 2 * i; if (child != h->size && h->data[child] > h->data[child+1]) { //如果左子节点非最后元素且>右子节点,则右子节点最小 child++; } if (temp > h->data[child]) { //如果temp大于当前元素的最小子节点,则将最小子节点赋值给父节点,否则跳出 h->data[i] = h->data[child]; } else { break; } } h->data[i] = temp;//将缓冲区值赋给当前游标 return result; }
堆排序
1 2 3 4 5 6 7 8 9 10 11 12
//堆排序 voidheap_sort(int a[], int n) { int i; heap* h = (heap*)malloc(sizeof(heap));//给堆指针分配空间 init(h);//初始化堆 for (i = 0; i < n; i++) {//将数组的元素依次插入堆 insert(h, a[i]); } for (i = 0; i < n; i++) { a[i] = deleteMin(h); } }
遍历输出数组
1 2 3 4 5 6 7 8
//遍历数组 voidtraverse_array(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ",a[i]); } printf("\n"); }
//创建一个小顶堆,size代表的是实际元素的个数 typedefstructMinHeap { int size; int data[MAX_SIZE]; } heap;
//初始化:数组0位置要空着 voidinit(heap* h ) { h->size = 0; }
//插入元素x intinsert(heap* h, int x) { int flag = 1; if (h->size == MAX_SIZE) { printf("heap is full!"); flag = 0; } int i; h->size++; for (i = h->size; i >= 1; i /= 2) { if(x < h->data[i / 2]) { h->data[i] = h->data[i/2]; } else { break; } } h->data[i] = x; return flag; }
//删除最小元素,在小顶堆即意味着删除根节点 intdeleteMin(heap* h) { int child; int result = h->data[1]; h->data[1] = h->data[h->size]; h->size--; int i = 1; int temp = h->data[1]; for (i = 1; 2 * i <= h->size; i = child) { child = 2 * i; if (child != h->size && h->data[child] > h->data[child+1]) { //如果左子节点非最后元素且>右子节点,则右子节点最小 child++; } if (temp > h->data[child]) { //如果temp大于当前元素的最小子节点,则将最小子节点赋值给父节点,否则跳出 h->data[i] = h->data[child]; } else { break; } } h->data[i] = temp;//将缓冲区值赋给当前游标 return result; }
//堆排序 voidheap_sort(int a[], int n) { int i; heap* h = (heap*)malloc(sizeof(heap));//给堆指针分配空间 init(h);//初始化堆 for (i = 0; i < n; i++) {//将数组的元素依次插入堆 insert(h, a[i]); } for (i = 0; i < n; i++) { a[i] = deleteMin(h); } } //遍历数组 voidtraverse_array(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ",a[i]); } printf("\n"); }
//主函数测试 intmain() { int a[] = {10,7,2,5,1}; int n = sizeof(a) / sizeof(int); traverse_array(a, n); heap_sort(a, n); traverse_array(a, n); }
小顶堆的实现方式(二)
堆的结构体
说明:有的时候不会像上面那样定义结构体,可能会用指针定义结构体,比如这样:
1 2 3 4 5
typedefstructMinHeap{ int *data;//表示堆的数组 大小要在用户输入的元素个数上+1 int Size;//数组里已有的元素(不包含a[0]) int Capacity; //数组的数量上限 }heap;//定义顶堆
//删除最小元素 intdeleteMin(heap* h){ int top = h->data[1]; int last = h->data[h->Size]; h->Size--; int i,child; for (i = 1; i * 2 <= h->Size; i = child) { child = i*2; //注意这里是存在右子节点 并且 右子节点比左子节点小 if (child!=h->Size && h->data[child] > h->data[child+1]) { child++; } //如果比右子节点还小 if (h->data[child]>last) { break; }else{//下滤 h->data[i] = h->data[child]; } } h->data[i] = last; return top; }
堆排序
1 2 3 4 5 6 7 8 9 10 11
//堆排序 voidheap_sort(int a[], int n) { int i; heap* h = init(n);//初始化堆 for (i = 0; i < n; i++) {//将数组的元素依次插入堆 insert(h, a[i]); } for (i = 0; i < n; i++) { a[i] = deleteMin(h); } }
遍历输出数组
1 2 3 4 5 6 7 8
//遍历数组 voidtraverse_array(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ",a[i]); } printf("\n"); }
#include<stdio.h> #include<stdlib.h> #define MinData -1//哨兵元素的值 typedefstructMinHeap{ int *data;//表示堆的数组 大小要在用户输入的元素个数上+1 int Size;//数组里已有的元素(不包含a[0]) int Capacity; //数组的数量上限 }heap;//定义顶堆
//创建堆 heap* init(int size){ heap* h = (heap*)malloc(sizeof(heap)); h->data = (int*)malloc(sizeof(int)*(size+1));//从a[1]开始保存数 所以数组数量要+1 h->Size = 0; h->Capacity = size; h->data[0] = MinData;//岗哨 return h; } //插入元素 intinsert(heap* h, int x){ //判断是否满了 if (h->Size == h->Capacity) { return0; } int i = ++h->Size; for (; i >= 1; i/=2) { if (h->data[i/2] > x) { h->data[i] = h->data[i/2]; } else { break; } } h->data[i] = x; return1; } //删除最小元素 intdeleteMin(heap* h){ int top = h->data[1]; int last = h->data[h->Size]; h->Size--; int i,child; for (i = 1; i * 2 <= h->Size; i = child) { child = i*2; //注意这里是存在右子节点 并且 右子节点比左子节点小 if (child!=h->Size && h->data[child] > h->data[child+1]) { child++; } //如果比右子节点还小 if (h->data[child]>last) { break; }else{//下滤 h->data[i] = h->data[child]; } } h->data[i] = last; return top; }
//堆排序 voidheap_sort(int a[], int n) { int i; heap* h = init(n);//初始化堆 for (i = 0; i < n; i++) {//将数组的元素依次插入堆 insert(h, a[i]); } for (i = 0; i < n; i++) { a[i] = deleteMin(h); } } //遍历数组 voidtraverse_array(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ",a[i]); } printf("\n"); }
//主函数测试 intmain() { int a[] = {10,7,2,5,1}; int n = sizeof(a) / sizeof(int); traverse_array(a, n); heap_sort(a, n); traverse_array(a, n); }