概念
a、二叉堆是一种完全二叉树(故而可以使用数组来保存)。二叉堆有最大二叉堆(父节点值永远大于任意子节点的值)和最小二叉堆两种(父节点的值永远小鱼任意子节点的值)。
b、二叉堆父子节点之间有大小关系,兄弟节点之间没有大小顺序关系。
用数组表示为 [开始符,5,6,7,12,8,9,8,13,14,9]
1、结构
// struct BinaryHeap { int* elements; //使用数组存储元素列表 int capacity; //数组的容量 int size; //当前的节点数 };
2、初始化
// BinaryHeapPointer bhp = (struct BinaryHeap*)malloc(sizeof(struct BinaryHeap)); bhp->capacity = ;//设置容量 bhp->size = 0; bhp->elements = malloc(sizeof(int) * (capacity + 1)); bhp->elements[0] = ; //设置一个标识让0下表元素再后续使用中被忽略 后面统一从1开始 计算更为方便
3、父节点与子节点的顺序关系
a. 父节点 = 子节点/2 向下取整
b. 子节点 = 父节点 * 2 & 子节点 = 父节点 * 2 + 1
4、插入数据
为了保证(实例最小二叉堆)父节点永远小于子节点值,插入时需要保证插入位置只大于父节点而小于子节点。(最大二叉堆也同理) 入下图所示 在原二叉堆中插入元素“14”在末尾处比父节点小,则与父节点交换,一直至比父节点大位置。
5、删除根节点
如下图所示,删除根节点(最小节点)将会失去根节点,此时应该将左右节点值对比,将较小值上移,被上移的节点同样失去值 需要将其2个子节点继续对比将最小值上移。。。。直至没有子节点可以上移。然后将最后一个节点移动至最后空出来的节点即可。
6、代码实现
// // // BinaryHeap.h // AVLTree // #ifndef BinaryHeap_h #define BinaryHeap_h #include <stdio.h> #define BinaryHeapValueType double struct BinaryHeap { int capacity; int size; BinaryHeapValueType* elements; }; typedef struct BinaryHeap* BinaryHeapPointer; BinaryHeapPointer binaryHeap_create(int capacity); void binaryHeap_insert(BinaryHeapPointer bhp, BinaryHeapValueType value); BinaryHeapValueType binaryHeap_deleteMin(BinaryHeapPointer bhp); #endif /* BinaryHeap_h */
// // BinaryHeap.c // AVLTree // // Created by sgf on 2017/8/26. // Copyright © 2017年 sgf. All rights reserved. // #include "BinaryHeap.h" #include <stdlib.h> #define START_VALUE 0 int binaryHeap_isFull(BinaryHeapPointer bhp) { return bhp->size >= bhp->capacity; } BinaryHeapPointer binaryHeap_create(int capacity) { BinaryHeapPointer bhp = (struct BinaryHeap*)malloc(sizeof(struct BinaryHeap)); bhp->capacity = capacity; bhp->size = 0; bhp->elements = malloc(sizeof(BinaryHeapValueType) * (capacity + 1)); bhp->elements[0] = START_VALUE; return bhp; } void binaryHeap_insert(BinaryHeapPointer bhp, BinaryHeapValueType value) { if(bhp==NULL) { return; } if(binaryHeap_isFull(bhp)) { return; } if(bhp->size<=1) { bhp->elements[ ++bhp->size ] = value; } else { int i ; for ( i = ++bhp->size ; bhp->elements[i/2] > value ; i = i/2) { bhp->elements[i] = bhp->elements[i/2]; } bhp->elements[i] = value; } } BinaryHeapValueType binaryHeap_deleteMin(BinaryHeapPointer bhp) { if(bhp==NULL) { return START_VALUE; } if(bhp->size == 0) { return START_VALUE; } BinaryHeapValueType minEl = bhp->elements[1]; BinaryHeapValueType lastEl = bhp->elements[bhp->size]; bhp->size--; int i , subNode; for(i=1; i*2 <= bhp->size; i = subNode) { subNode = i * 2 ; if(subNode !=bhp->size && bhp->elements[subNode] > bhp->elements[subNode + 1] ) { subNode++; } if(lastEl> bhp->elements[subNode]) bhp->elements[i] = bhp->elements[subNode] ; else break; } bhp->elements[i] = lastEl; return minEl; } //----------应用---------- //----------------------- //----------------------- //----------------------- //将所有元素移除,并在数组中实现排序 void binaryHeap_sort2Desc(BinaryHeapPointer bhp) { while (bhp->size>0) { BinaryHeapValueType v = binaryHeap_deleteMin(bhp); bhp->elements[bhp->size + 1] = v; } }
//根据一个数组,创建一个二叉堆 void binaryHeap_createWithArray_sort(int a[], int len, int index) { //根节点 if(index > len/2+1) { return; } //左下最大 if( a[ index * 2 ] < a[index] && a[index * 2 ] < a[index * 2 + 1 ] ) { int tmp = a[index]; a[index] = a[index * 2]; a[index * 2] = tmp; binaryHeap_createWithArray_sort(a, len, index * 2); } //右下最大 else if( a[ index * 2 + 1 ] < a[index] && a[index * 2 + 1] < a[index * 2 ] ) { int tmp = a[index]; a[index] = a[index * 2 + 1]; a[index * 2 + 1] = tmp; binaryHeap_createWithArray_sort(a, len, index * 2 + 1); } }