1.堆的概念 如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆 2.堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 3.堆的实现 头文件代码
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int HPDataType; typedef struct Heap { //用来存放堆中元素 HPDataType* _array; int _capacity;//堆的容量 int _size;//堆中有效元素个数 }Heap; //扩容函数 void CheckCapacity(Heap* hp); //交换函数 void Swap(HPDataType* Left, HPDataType* Right); //向下排序 void adjustdown(HPDataType* array, int size, int parent); //向上排序 void adjustup(HPDataType* array, int size, int child); // 用数组初始化堆 void InitHeap(Heap* hp, HPDataType* array, int size); // 初始化一个空堆 void InitEmptyHeap(Heap* hp, int capacity); // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, HPDataType data); // 删除堆顶元素 void EraseHeap(Heap* hp); // 获取堆中有效元素个数 int HeapSize(Heap* hp); // 检测堆是否为空堆 int HeapEmpty(Heap* hp); // 获取堆顶元素 HPDataType HeapTop(Heap* hp); // 销毁堆 void DestroyHeap(Heap* hp);实现代码
#include "heap.h" //交换函数 void Swap(HPDataType* Left, HPDataType* Right) { //使用指针进行操作,******传值传址 HPDataType temp = *Left; *Left = *Right; *Right = temp; } //向下排序 void adjustdown(HPDataType* array, int size, int parent) { //根据堆的性质,对于完全二叉树,若从上至下,从左至右编号,则编号为i的结点, //其左孩子编号必为2i,其右孩子编号必为2i+1,其双亲编号必为i/2(根节点除外) int child = 2*parent + 1; while (child < size) { //判断堆的左右孩子的大小 if (array[child] > array[child + 1]&&child+1<size) { child = child + 1; } //用最小的孩子和根节点进行比较,如果小于根节点,交换两个节点 if (array[child] < array[parent]) { Swap(&array[parent], &array[child]); parent = child; child = 2 * parent + 1; } else { return; } } return; } //向上排序 void adjustup(HPDataType* array, int size, int child) { int parent = ((child - 1) >> 1); while (parent >= 0) { if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); child = parent; parent = ((child - 1) >> 1); } else { return; } } return; } //扩容函数 void CheckCapacity(Heap* hp) { assert(hp); if (hp->_size == hp->_capacity) { //默认扩容倍数为2倍,扩容的四步走 int newcapacity = hp->_capacity * 2; //创建新数组 HPDataType* newarray = (HPDataType*)malloc(sizeof(HPDataType)*newcapacity); if (newarray == NULL) { assert(newarray); return; } //把旧堆元素,转移到新堆 for (int i = 0; i < hp->_size; ++i) { newarray[i] = hp->_array[i]; } //释放旧堆 free(hp->_array); //指针指向新堆 hp->_array = newarray; //改变堆的容量 hp->_capacity = newcapacity; } } // 用数组初始化堆 void InitHeap(Heap* hp, HPDataType* array, int size) { assert(hp); //给堆的数组开辟空间 hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (hp->_array == NULL) { assert(hp->_array); return; } //把数组中的元素,全部转移到堆的数组中 hp->_capacity = size; for (int i = 0; i < size; ++i) { hp->_array[i] = array[i]; } hp->_size = size; //对这个数组进行调整,使其成为一个堆 int root = (size - 2) >> 1; for (; root >= 0; --root) { adjustdown(hp->_array, size, root); } } // 初始化一个空堆 void InitEmptyHeap(Heap* hp, int capacity) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*hp->_capacity); if (hp->_array == NULL) { assert(hp->_array); return; } hp->_size = 0; hp->_capacity = capacity; } // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, HPDataType data) { assert(hp); //判断是否需要扩容 CheckCapacity(hp); //插入元素,默认堆尾插入 hp->_array[hp->_size] = data; hp->_size++; //给元素进行位置调整 adjustup(hp->_array, hp->_size, hp->_size - 1); } // 删除堆顶元素 void EraseHeap(Heap* hp) { assert(hp); //把堆顶元素和堆的最后一个元素交换位置 Swap(hp->_array[0], hp->_array[hp->_size - 1]); //有效元素减一,即最后一个元素被去除 hp->_size--; adjustdown(hp->_array, hp->_size, 0); } // 获取堆中有效元素个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 检测堆是否为空堆 int HeapEmpty(Heap* hp) { assert(hp); return 0 == hp->_size; } // 获取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); return hp->_array[0]; } // 销毁堆 void DestroyHeap(Heap* hp) { if (hp == NULL) { return; } free(hp->_array); hp->_array = NULL; hp->_size = 0; hp->_capacity = 0; }测试代码
#include "heap.h" #include <time.h> int main() { Heap hp; srand((unsigned)time(NULL)); int arr[20]; for (int i = 0; i < 20; ++i) { arr[i] = rand() % 21; } InitHeap(&hp, (HPDataType*)arr, 20); printf("%d\n", HeapSize(&hp)); printf("%d\n", HeapTop(&hp)); system("pause"); return 0; }