做网站好不好,网站开发 链接指向文件夹,wordpress相关推荐代码,qq网页版在线直接登录目录 大小堆
堆的实现
堆的创建
堆的销毁
交换
向上调整
向下调整
弹出首个元素
取出首个元素
判空
堆插入 大小堆
大堆#xff1a;最上面的数字是最小的#xff0c;越往下越大
小堆#xff1a;最上面的数字是最大的#xff0c;越往下越小
堆的复杂程度#…
目录 大小堆
堆的实现
堆的创建
堆的销毁
交换
向上调整
向下调整
弹出首个元素
取出首个元素
判空
堆插入 大小堆
大堆最上面的数字是最小的越往下越大
小堆最上面的数字是最大的越往下越小
堆的复杂程度
由错位相减我们可以知道Tn n - log(n-1) n,所以建堆的复杂程度为ON
堆的实现
堆的创建
void HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}堆的销毁
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
交换 void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}向上调整 void Adjustup(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;int parent (child - 1) / 2;}else{break;}}
}
向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 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 parent * 2 1;}else {break;}}
}弹出首个元素
void HPPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}取出首个元素
HPDataType HPTop(HP* php)
{assert(php);assert(php-size);return php-a[0];
}判空 bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}
堆插入 void HPPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity (php-capacity php-size 0 ? 4 : php-capacity * 2);HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));//扩建的是字节if (tmp NULL){printf(malloc faild);return;}}php-a[php-size] x;php-size;Adjustup(php-a, php-size - 1);
}
