网站建设公司销售技巧,百度网盘网页,免费封面设计在线制作生成,百度热搜大数据堆的数据结构
对于堆, 有最大堆和最小堆, 在定义一个堆的时候用一个数组表示堆, 同时为了方便定义堆的大小, 用一个 size 表示堆的有效元素, 同时为了区别最大堆和最小堆, 我们用一个函数指针表示这个堆是最大堆还是最小堆.
typedef int (*Compare)(HeapType parent, HeapTyp…堆的数据结构
对于堆, 有最大堆和最小堆, 在定义一个堆的时候用一个数组表示堆, 同时为了方便定义堆的大小, 用一个 size 表示堆的有效元素, 同时为了区别最大堆和最小堆, 我们用一个函数指针表示这个堆是最大堆还是最小堆.
typedef int (*Compare)(HeapType parent, HeapType child); typedef struct Heap { HeapType data[HeapMaxSize]; int size; Compare cmp;
} Heap;
堆的初始化
int Greater(HeapType parent, HeapType child)
{return parent child? 1 : 0;
}
int Less(HeapType parent, HeapType child)
{return parent child ? 1 : 0;
}
void HeapInit(Heap* heap, Compare cmp)
{if(heap NULL){return;}heap - size 0;heap - cmp cmp;
}
堆的插入
先将要插入得到元素插入到堆对应的数组的最后一个位置, 然后判断插入结点的值和它的父节点是否符合堆的特征(最大堆:根节点大于它的左孩子和有孩子, 最小堆根节点小于它的左孩子和有孩子), 此时如果插入结点和它的父节点符合堆的特性就直接退出, 如果根节点和父节点不符合堆的特性, 此时就需要将插入结点和它的根节点进行交换, 直到符合堆的特性为止
void HeapInsert(Heap* heap, HeapType value)
{if(heap NULL){return;//非法输入}if(heap - size HeapMaxSize){return;}//先将 value 插入到末尾heap - data[heap - size] value;//判断父节点和 value 是否符合规定int child heap - size - 1;int parent (child - 1) / 2;while(child 0){//如果不符合, 就直接将插入的结点和它的父节点进行交换if(heap - cmp(heap - data[parent], heap - data[child]) 0){Swap(heap - data[parent], heap - data[child]);child parent;parent (child -1) / 2;}//如果符合, 就退出else{break;}}
}
取堆顶元素
直接返回堆对用的数组的第一个元素
int HeapRoot(Heap* heap, HeapType* value)
{if(heap NULL || value NULL){return 0;}*value heap - data[0];return 1;
}
删除堆
先将堆的最后一个元素和堆的第一个结点进行交换, 将堆的大小减1, 此时由于交换了两个元素, 因此可能会破坏堆的结构.先判断父节点是否有右孩子, 如果有右孩子, 就将左右孩子中比较满足多结构的一个标记下来, 接着判断父节点和左右孩子较满足堆结构的的结点是否需要交换, 如果需要交换就将两个交换, 否则就直接退出
void HeapErase(Heap* heap)
{if(heap NULL){return;}if(heap - size 0){return;}//将对顶元素和最后一个元素进行交换Swap(heap - data[0], heap - data[heap - size - 1]);--heap - size;int parent 0;int child 2 * parent 1;while(parent 0 parent heap - size child 0 child heap - size){//判断是否有右子树if(child 1 heap - size){//判断出左右孩子中较满足对特性的一个元素if(heap - cmp(heap - data[child], heap - data[child 1]) 0){child child 1;}//判断是否需要下沉if(heap - cmp(heap - data[parent], heap - data[child]) 0){Swap(heap - data[parent], heap - data[child]);parent child;child 2 * parent 1;}else if(heap - cmp(heap - data[parent], heap - data[child]) 1){return;}}else{return;}}
}
堆的判空
判断堆所对应的的数组元素的个数是否为空, 如果为空就返回1, 否则就返回0 int HeapEmpty(Heap* heap)
{if(heap NULL){return 1;}if(heap - size 0){return 1;}return 0;
}
判断堆的元素的个数
int HeapSize(Heap* heap)
{if(heap NULL){return 0;}return heap - size;
}
堆的销毁
void HeapDestroy(Heap* heap)
{if(heap NULL){return;}heap - size 0;heap - cmp NULL;
}
堆排序
给定一个数组, 将这个数组按照对应的规则进行排序. 即先定义一个堆, 再将数组中的所有元素插入到堆中, 将堆中的元素删除, 最后恢复对的有效元素, 将堆中的内容全部拷贝到数组中 void HeapSort(HeapType array[], int size, Compare cmp)
{if(array NULL || size 0){return;}Heap heap;HeapInit(heap, cmp);//先将数组中的元素插入到堆中int i 0;for(; i size; i){HeapInsert(heap, array[i]);}//删除对中的所有元素for(i 0; i size; i){HeapErase(heap);}heap.size size;for(i 0; i size; i){array[i] heap.data[i];}
}
