二项堆的C语言实现
二项堆是一种比较复杂的堆结构，这种数据结构在"算法-c语言实现(第3版)"中有讲解，可惜这本书实在把二项堆说得云山雾罩。
二项堆是二项树的集合。下面先说明二项树再说明二项堆及其各种操作。
二项树
二项树是一种递归定义的树，它的定义如下：
- 二项树B0只有一个节点。
- 二项树Bk由两棵二项树B(K-1)组成，其中一棵树是另一棵树的最左孩子。
如下图所示：
上图的B0,B1,B2,B3,B4都是二项树，B0有一节点，B1由两B0组成，B2由两B1组成，B3由两B2组成，B4由两B3组成；而且，当两颗相同的二项树组成一棵树时，其中一棵树是另一棵树的最左孩子。
二项树有如下性质：
- BK共有2^K个节点
- BK的高度是K
- BK在深度i处有C(K,i)个节点，其中i=0,1,2,....,K
- 根的度为K，它大于任何其它节点的度数
二项堆
二项堆一般用来实现优先队列，是由满足以下性质的二项树构成：
- 每棵二项树都满足堆的性质
- 不能有两棵以上的二项树具有相同的度数。即在二项堆中，度数为K的二项树有0个或1个。
上图就是一棵二项堆。它由3棵二项树组成。 可以将包含n个节点的二项堆，表示成若干个2的指数和(或者转换成二进制)，则每一个2个指数都对应一棵二项树。例如，13(二进制是1101)的2个指数和为13=23 + 22 + 20, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成。
二项堆的数据结构及ADT
typedef struct binomial_node_s *binomial_node_pt;
typedef struct binomial_node_s {
binomial_node_pt parent; //父节点
binomial_node_pt leftchild; //左孩子
binomial_node_pt sibling; //兄弟节点
int degree; //度数
Item data; //数据
} binomial_node_t;
binomial_node_pt binomial_heap_union(binomial_node_pt h1, binomial_node_pt h2);
binomial_node_pt binomial_heap_push(binomial_node_pt heap, Item element);
void binomial_heap_update(binomial_node_pt heap, Item oldelement, Item newelement);
binomial_node_pt binomial_heap_find(binomial_node_pt heap, Item element);
binomial_node_pt binomial_heap_top(binomial_node_pt heap);
binomial_node_pt binomial_heap_pop(binomial_node_pt heap);
binomial_node_pt binomial_heap_delete(binomial_node_pt heap, Item element);
void binomial_heap_destroy(binomial_node_pt heap);
void binomial_heap_print(binomial_node_pt heap);
void binomial_heap_export_dot(binomial_node_pt heap, char *filename, char *label);
合并操作
合并操作是二项堆的重点，二项堆的添加操作也是基于合并操作来实现的。
合并两个二项堆，需要的步骤如下：
- 将两个二项堆的根链表合并成一个链表。合并后的新链表按照"节点的度数"单调递增排列。
- 将新链表中"根节点度数相同的二项树"连接起来，直到所有根节点度数都不相同。
合并操作示意图
以下为实现代码
static binomial_node_pt
binomial_tree_link(binomial_node_pt t1, binomial_node_pt t2)
{
if (item_cmp(t1->data, t2->data)) {
t1->sibling = t2->leftchild;
t1->parent = t2;
t2->leftchild = t1;
t2->degree++;
return t2;
}
else {
t2->sibling = t1->leftchild;
t2->parent = t1;
t1->leftchild = t2;
t1->degree++;
return t1;
}
}
static binomial_node_pt
binomial_heap_merge(binomial_node_pt h1, binomial_node_pt h2)
{
binomial_node_pt head = NULL;
binomial_node_pt *pos = &head;
while (h1 && h2) {
if (h1->degree < h2->degree) {
*pos = h1;
h1 = h1->sibling;
}
else {
*pos = h2;
h2 = h2->sibling;
}
pos = &(*pos)->sibling;
}
if (h1 == NULL) {
*pos = h2;
}
else {
*pos = h1;
}
return head;
}
binomial_node_pt
binomial_heap_union(binomial_node_pt h1, binomial_node_pt h2)
{
binomial_node_pt heap, pos, *pos_pt, next;
heap = binomial_heap_merge(h1, h2);
if (heap == NULL) {
return NULL;
}
pos_pt = &heap;
pos = *pos_pt;
while (pos != NULL && pos->sibling != NULL) {
if ((pos->degree == pos->sibling->degree) &&
(pos->sibling->sibling==NULL || pos->degree != pos->sibling->sibling->degree)) {
next = pos->sibling->sibling;
*pos_pt = binomial_tree_link(pos, pos->sibling);
(*pos_pt)->sibling = next;
}
else {
pos_pt = &(*pos_pt)->sibling;
}
pos = *pos_pt;
}
return heap;
}
binomial_heap_merge的作用就是"两个二项堆的根链表合并成一个链表，合并后的新链表按照'节点的度数'单调递增排序"。
binomial_tree_link则是为了合并操作的辅助函数，它的作用是将两个根节点度数相同的二项树连接起来。
删除操作
删除二项堆中的某个节点，需要的步骤如下：
- 将"该节点"交换到"它所在二项树"的根节点位置。方法是，从"该节点"不断向上(即向树根方向)"遍历，不断交换父节点和子节点的数据，直到被删除的键值到达树根位置
- 将"该节点所在的二项树"从二项堆中移除
- 将"该节点所在的二项树"进行反转。反转的意思，就是将根的所有孩子独立出来，并将这些孩子整合成二项堆，将该二项堆记为child。
- 将child和heap进行合并操作。
删除操作示意图
以下为实现代码
static binomial_node_pt
binomial_reverse(binomial_node_pt node)
{
binomial_node_pt heap=NULL, temp;
while (node != NULL) {
temp = node;
node = node->sibling;
temp->sibling = heap;
temp->parent = NULL;
heap = temp;
}
return heap;
}
binomial_node_pt
binomial_heap_delete(binomial_node_pt heap, Item element)
{
binomial_node_pt node, pre_head, pos, child;
node = binomial_heap_find(heap, element);
while (node == NULL) {
return heap;
}
while (node->parent != NULL) {
swap(&node->data, &node->parent->data);
node = node->parent;
}
pre_head = NULL;
pos = heap;
while (pos != node && pos != NULL) {
pre_head = pos;
pos = pos->sibling;
}
if (pre_head != NULL) {
pre_head->sibling = node->sibling;
}
else {
heap = node->sibling;
}
child = binomial_reverse(node->leftchild);
heap = binomial_heap_union(heap, child);
free(node);
return heap;
}
binomial_reverse的作用是反转二项堆，并返回反转之后的根节点。
删除顶端元素
这个操作与删除操作相似，差别只是删除节点已经在树的根节点上，所以不再需要向上遍历。
以下为实现代码
binomial_node_pt
binomial_heap_pop(binomial_node_pt heap)
{
binomial_node_pt node, pre_node, child;
if (heap == NULL) {
return NULL;
}
_binomial_heap_top(heap, &pre_node, &node);
if (pre_node == NULL) {
heap = node->sibling;
}
else {
pre_node->sibling = node->sibling;
}
child = binomial_reverse(node->leftchild);
heap = binomial_heap_union(heap, child);
free(node);
return heap;
}
更新操作
更新二项堆中的某个节点，就是修改节点的值，它包括两部分分："向上调整" 和 "向下调整"
更新操作实现代码：
void
binomial_heap_update(binomial_node_pt heap, Item oldelement, Item newelement)
{
binomial_node_pt node;
node = binomial_heap_find(heap, oldelement);
if (item_cmp(oldelement, newelement)) {
binomial_tree_update_up(node, newelement);
}
else {
binomial_tree_update_down(node, newelement);
}
}
向上调整很简单：需要更新的节点位于一棵二项树中；不断的将该节点上调，以至树符合二项树的规则。
更新操作向上调整示意图
以下为实现代码
/*
* Name: binomial_tree_update_up
* Description: 更新高优先级数据后，向上调整二项树
*
*/
static void
binomial_tree_update_up(binomial_node_pt node, Item element)
{
binomial_node_pt pos;
if (node == NULL) {
return;
}
node->data = element;
pos = node;
while (pos->parent != NULL && item_cmp(pos->parent->data, pos->data)) {
swap(&pos->data, &pos->parent->data);
pos = pos->parent;
}
}
向下调整也类似，需要更新的节点位于一棵二项树中；不断的将该节点下调，以至树符合二项树的规则。主要的区别是要从节点的所有子树中选择一个节点作为下调目标节点。
以下为实现代码
/*
* Name: binomial_tree_update_down
* Description: 更新低优先级数据后，向下调整二项树
*
*/
static void
binomial_tree_update_down(binomial_node_pt node, Item element)
{
binomial_node_pt pos, child, best_child;
if (node == NULL) {
return;
}
node->data = element;
pos = node;
while (pos->leftchild != NULL) {
child = pos->leftchild;
best_child = child;
while (child != NULL) {
if (item_cmp(best_child->data, child->data)) {
best_child = child;
}
child = child->sibling;
}
if (best_child == NULL || item_cmp(best_child->data, pos->data)) {
return;
}
swap(&pos->data, &best_child->data);
pos = best_child;
}
}
完整源码
/* binomial_heap.h */
#ifndef BINOMIAL_HEAP_H
#define BINOMIAL_HEAP_H
typedef int Item;
typedef struct binomial_node_s *binomial_node_pt;
typedef struct binomial_node_s {
binomial_node_pt parent;
binomial_node_pt leftchild;
binomial_node_pt sibling;
int degree;
Item data;
} binomial_node_t;
binomial_node_pt binomial_heap_union(binomial_node_pt h1, binomial_node_pt h2);
binomial_node_pt binomial_heap_push(binomial_node_pt heap, Item element);
void binomial_heap_update(binomial_node_pt heap, Item oldelement, Item newelement);
binomial_node_pt binomial_heap_find(binomial_node_pt heap, Item element);
binomial_node_pt binomial_heap_top(binomial_node_pt heap);
binomial_node_pt binomial_heap_pop(binomial_node_pt heap);
binomial_node_pt binomial_heap_delete(binomial_node_pt heap, Item element);
void binomial_heap_destroy(binomial_node_pt heap);
void binomial_heap_print(binomial_node_pt heap);
void binomial_heap_export_dot(binomial_node_pt heap, char *filename, char *label);
#endif
binomial_heap.h
/*
* =====================================================================================
*
* Filename: binomial_heap.c
*
* Description: 二项堆实现
*
* Version: 1.0
* Created: 2016-09-26 20:13
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "binomial_heap.h"
/*
* 最小堆 ((a) > (b))
* 最大堆 ({a} < (b))
*
*/
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
#define item_equal(a, b) ((a) == (b)) /* 检查是否相等 */
static void swap(Item *p1, Item *p2);
static binomial_node_pt binomial_node_new(Item data);
static binomial_node_pt binomial_tree_link(binomial_node_pt t1, binomial_node_pt t2);
static binomial_node_pt binomial_heap_merge(binomial_node_pt h1, binomial_node_pt h2);
static void binomial_tree_update_up(binomial_node_pt node, Item element);
static void binomial_tree_update_down(binomial_node_pt node, Item element);
static void
swap(Item *p1, Item *p2)
{
Item temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
static binomial_node_pt
binomial_node_new(Item data)
{
binomial_node_pt node;
node = (binomial_node_pt)malloc(sizeof(binomial_node_t));
if (node == NULL)
{
printf("malloc binomial node failed!\n");
return NULL;
}
node->parent = NULL;
node->leftchild = NULL;
node->sibling = NULL;
node->degree = 0;
node->data = data;
return node;
}
static binomial_node_pt
binomial_tree_link(binomial_node_pt t1, binomial_node_pt t2)
{
if (item_cmp(t1->data, t2->data)) {
t1->sibling = t2->leftchild;
t1->parent = t2;
t2->leftchild = t1;
t2->degree++;
return t2;
}
else {
t2->sibling = t1->leftchild;
t2->parent = t1;
t1->leftchild = t2;
t1->degree++;
return t1;
}
}
static binomial_node_pt
binomial_heap_merge(binomial_node_pt h1, binomial_node_pt h2)
{
binomial_node_pt head = NULL;
binomial_node_pt *pos = &head;
while (h1 && h2) {
if (h1->degree < h2->degree) {
*pos = h1;
h1 = h1->sibling;
}
else {
*pos = h2;
h2 = h2->sibling;
}
pos = &(*pos)->sibling;
}
if (h1 == NULL) {
*pos = h2;
}
else {
*pos = h1;
}
return head;
}
binomial_node_pt
binomial_heap_union(binomial_node_pt h1, binomial_node_pt h2)
{
binomial_node_pt heap, pos, *pos_pt, next;
heap = binomial_heap_merge(h1, h2);
if (heap == NULL) {
return NULL;
}
pos_pt = &heap;
pos = *pos_pt;
while (pos != NULL && pos->sibling != NULL) {
if ((pos->degree == pos->sibling->degree) &&
(pos->sibling->sibling==NULL || pos->degree != pos->sibling->sibling->degree)) {
next = pos->sibling->sibling;
*pos_pt = binomial_tree_link(pos, pos->sibling);
(*pos_pt)->sibling = next;
}
else {
pos_pt = &(*pos_pt)->sibling;
}
pos = *pos_pt;
}
return heap;
}
binomial_node_pt
binomial_heap_find(binomial_node_pt heap, Item element)
{
binomial_node_pt temp;
if (heap == NULL) {
return NULL;
}
if (item_equal(heap->data, element)) {
return heap;
}
if ((temp = binomial_heap_find(heap->sibling, element)) != NULL) {
return temp;
}
if ((temp = binomial_heap_find(heap->leftchild, element)) != NULL) {
return temp;
}
return NULL;
}
binomial_node_pt
binomial_heap_push(binomial_node_pt heap, Item element)
{
binomial_node_pt node;
node = binomial_node_new(element);
if (node == NULL) {
return heap;
}
return binomial_heap_union(heap, node);
}
/*
* Name: binomial_tree_update_up
* Description: 更新高优先级数据后，向上调整二项树
*
*/
static void
binomial_tree_update_up(binomial_node_pt node, Item element)
{
binomial_node_pt pos;
if (node == NULL) {
return;
}
node->data = element;
pos = node;
while (pos->parent != NULL && item_cmp(pos->parent->data, pos->data)) {
swap(&pos->data, &pos->parent->data);
pos = pos->parent;
}
}
/*
* Name: binomial_tree_update_down
* Description: 更新低优先级数据后，向下调整二项树
*
*/
static void
binomial_tree_update_down(binomial_node_pt node, Item element)
{
binomial_node_pt pos, child, best_child;
if (node == NULL) {
return;
}
node->data = element;
pos = node;
while (pos->leftchild != NULL) {
child = pos->leftchild;
best_child = child;
while (child != NULL) {
if (item_cmp(best_child->data, child->data)) {
best_child = child;
}
child = child->sibling;
}
if (best_child == NULL || item_cmp(best_child->data, pos->data)) {
return;
}
swap(&pos->data, &best_child->data);
pos = best_child;
}
}
void
binomial_heap_update(binomial_node_pt heap, Item oldelement, Item newelement)
{
binomial_node_pt node;
node = binomial_heap_find(heap, oldelement);
if (item_cmp(oldelement, newelement)) {
binomial_tree_update_up(node, newelement);
}
else {
binomial_tree_update_down(node, newelement);
}
}
static void
_binomial_heap_top(binomial_node_pt heap, binomial_node_pt *pre_tree, binomial_node_pt *tree)
{
*pre_tree = NULL;
*tree = heap;
if (heap == NULL) {
return;
}
while (heap->sibling != NULL) {
if (item_cmp((*tree)->data, heap->sibling->data)) {
*pre_tree = heap;
*tree = heap->sibling;
heap = heap->sibling;
}
}
return;
}
binomial_node_pt
binomial_heap_top(binomial_node_pt heap)
{
binomial_node_pt node, pre_node;
_binomial_heap_top(heap, &pre_node, &node);
return node;
}
static binomial_node_pt
binomial_reverse(binomial_node_pt node)
{
binomial_node_pt heap=NULL, temp;
while (node != NULL) {
temp = node;
node = node->sibling;
temp->sibling = heap;
temp->parent = NULL;
heap = temp;
}
return heap;
}
binomial_node_pt
binomial_heap_pop(binomial_node_pt heap)
{
binomial_node_pt node, pre_node, child;
if (heap == NULL) {
return NULL;
}
_binomial_heap_top(heap, &pre_node, &node);
if (pre_node == NULL) {
heap = node->sibling;
}
else {
pre_node->sibling = node->sibling;
}
child = binomial_reverse(node->leftchild);
heap = binomial_heap_union(heap, child);
free(node);
return heap;
}
binomial_node_pt
binomial_heap_delete(binomial_node_pt heap, Item element)
{
binomial_node_pt node, pre_head, pos, child;
node = binomial_heap_find(heap, element);
while (node == NULL) {
return heap;
}
while (node->parent != NULL) {
swap(&node->data, &node->parent->data);
node = node->parent;
}
pre_head = NULL;
pos = heap;
while (pos != node && pos != NULL) {
pre_head = pos;
pos = pos->sibling;
}
if (pre_head != NULL) {
pre_head->sibling = node->sibling;
}
else {
heap = node->sibling;
}
child = binomial_reverse(node->leftchild);
heap = binomial_heap_union(heap, child);
free(node);
return heap;
}
void
binomial_heap_destroy(binomial_node_pt heap)
{
if (heap == NULL) {
return;
}
binomial_heap_destroy(heap->leftchild);
binomial_heap_destroy(heap->sibling);
free(heap);
}
static void
binomial_tree_printnode(binomial_node_pt node, int h)
{
int i;
for (i=0; i < h; i++) {
printf(" ");
}
if (node == NULL) {
printf("*\n");
}
else {
printf("%d\n", node->data);
}
}
static void
binomial_tree_show(binomial_node_pt tree, int h)
{
if (h == 0) {
printf("---------------------------\n");
}
if (tree == NULL) {
binomial_tree_printnode(NULL, h);
return;
}
binomial_tree_show(tree->leftchild, h+1);
binomial_tree_printnode(tree, h);
binomial_tree_show(tree->sibling, h);
}
void
binomial_heap_print(binomial_node_pt heap)
{
binomial_tree_show(heap, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, binomial_node_pt heap, char *last_label, char *tree_first_label)
{
/* 打印节点 */
char node_name[10] = {0};
if (heap == NULL) {
return;
}
sprintf(node_name, "n%d", node_num);
if (last_label == NULL) {
strcpy(tree_first_label, node_name);
}
fprintf(fp, "%s[label=%d, xlabel=%d];\n", node_name, heap->data, heap->degree);
node_num++;
/* 打印边 */
if (last_label != NULL) {
if (heap->sibling == NULL) {
fprintf(fp, "%s->%s[weight=100];\n", last_label, node_name);
}
else {
fprintf(fp, "%s->%s;\n", last_label, node_name);
}
}
/* 打印子节点 */
if (heap->leftchild == NULL && heap->sibling == NULL) {
return;
}
/* 打印兄弟节点 */
if (last_label != NULL) {
export_dot(fp, heap->sibling, last_label, tree_first_label);
}
/* 打印子节点 */
export_dot(fp, heap->leftchild, node_name, tree_first_label);
}
void
binomial_heap_export_dot(binomial_node_pt heap, char *filename, char *label)
{
FILE *fp;
binomial_node_pt tree;
int cluster_num = 0;
char tree_name[10] = {0};
char last_tree_name[10] = {0};
fp = fopen(filename, "w");
fprintf(fp, "digraph g{\nnode[shape=circle];\nlabel=\"%s\";\nlabeljust=l;\nlabelloc=t;\n", label);
tree = heap;
while (tree != NULL) {
fprintf(fp, "subgraph cluster_%d {\npencolor=green;label=\"二项树%d\";\n", cluster_num, cluster_num);
strcpy(last_tree_name, tree_name);
memset(tree_name, 0, sizeof(tree_name)/sizeof(char));
export_dot(fp, tree, NULL, tree_name);
cluster_num++;
fprintf(fp, "}\n");
if (strlen(tree_name) > 0 && strlen(last_tree_name) > 0) {
fprintf(fp, "%s->%s[constraint=false];\n", last_tree_name, tree_name);
}
tree = tree->sibling;
}
fprintf(fp, "}\n");
fclose(fp);
}
binomial_heap.c
/* binomial_heap_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "binomial_heap.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int a[]= {42,20,35,18,31,9,23,6,52,24,48,11,13};
int b[]= {25,15,12,7,33,28,41};
int i;
int alen=LENGTH(a);
int blen=LENGTH(b);
binomial_node_pt ha=NULL, hb=NULL, hc=NULL, temp=NULL;
printf("== 二项堆(ha)中依次添加: ");
for(i=0; i<alen; i++)
{
printf("%d ", a[i]);
ha = binomial_heap_push(ha, a[i]);
}
printf("\n== 二项堆(ha)的详细信息: \n");
binomial_heap_print(ha);
printf("\n== 二项堆(hb)中依次添加: ");
for(i=0; i<blen; i++)
{
printf("%d ", b[i]);
hb = binomial_heap_push(hb, b[i]);
}
printf("\n== 二项堆(hb)的详细信息: \n");
binomial_heap_print(hb);
hc = binomial_heap_union(ha, hb);
printf("\n== 合并ha和hb后的详细信息: \n");
binomial_heap_print(hc);
binomial_heap_export_dot(hc, "union.dot", "合并结果");
binomial_heap_destroy(hc);
ha = NULL;
for(i=0; i<alen; i++)
{
ha = binomial_heap_push(ha, a[i]);
}
printf("== 二项堆(ha)中节点值20减少为2: ");
binomial_heap_update(ha, 20, 2);
printf("\n== 二项堆ha中节点20减少为2后详细信息: \n");
binomial_heap_print(ha);
binomial_heap_export_dot(ha, "update_up.dot", "节点值减少");
binomial_heap_destroy(ha);
ha = NULL;
for(i=0; i<alen; i++)
{
ha = binomial_heap_push(ha, a[i]);
}
printf("== 二项堆(ha)中节点值6增加为60: ");
binomial_heap_update(ha, 6, 60);
printf("\n== 二项堆ha中节点6增加为60后详细信息: \n");
binomial_heap_print(ha);
binomial_heap_export_dot(ha, "update_down.dot", "节点值增加");
binomial_heap_destroy(ha);
ha = NULL;
for(i=0; i<alen; i++)
{
ha = binomial_heap_push(ha, a[i]);
}
temp = binomial_heap_top(ha);
printf("== 二项堆(ha)中最优节点值: %d", temp->data);
ha = binomial_heap_pop(ha);
printf("\n== 二项堆ha中弹出最优节点: \n");
binomial_heap_print(ha);
binomial_heap_export_dot(ha, "pop.dot", "弹出最优节点");
binomial_heap_destroy(ha);
ha = NULL;
for(i=0; i<alen; i++)
{
ha = binomial_heap_push(ha, a[i]);
}
ha = binomial_heap_delete(ha, 20);
printf("\n== 二项堆ha中删除节点20: \n");
binomial_heap_print(ha);
binomial_heap_export_dot(ha, "delete.dot", "删除节点");
binomial_heap_destroy(ha);
return 0;
}
binomial_heap_test.c
测试程序的运行结果
== 二项堆(ha)中依次添加: 42 20 35 18 31 9 23 6 52 24 48 11 13
== 二项堆(ha)的详细信息:
---------------------------
*
13
---------------------------
*
52
*
24
*
48
*
11
---------------------------
*
42
*
20
*
35
*
18
*
31
*
9
*
23
*
6
---------------------------
*
== 二项堆(hb)中依次添加: 25 15 12 7 33 28 41
== 二项堆(hb)的详细信息:
---------------------------
*
41
---------------------------
*
33
*
28
---------------------------
*
25
*
15
*
12
*
7
---------------------------
*
== 合并ha和hb后的详细信息:
---------------------------
*
33
*
28
*
41
*
13
---------------------------
*
52
*
24
*
48
*
11
*
25
*
15
*
12
*
7
*
42
*
20
*
35
*
18
*
31
*
9
*
23
*
6
---------------------------
*
== 二项堆(ha)中节点值20减少为2:
== 二项堆ha中节点20减少为2后详细信息:
---------------------------
*
13
---------------------------
*
52
*
24
*
48
*
11
---------------------------
*
42
*
18
*
35
*
6
*
31
*
9
*
23
*
2
---------------------------
*
== 二项堆(ha)中节点值6增加为60:
== 二项堆ha中节点6增加为60后详细信息:
---------------------------
*
13
---------------------------
*
52
*
24
*
48
*
11
---------------------------
*
42
*
20
*
60
*
35
*
31
*
9
*
23
*
18
---------------------------
*
== 二项堆(ha)中最优节点值: 6
== 二项堆ha中弹出最优节点:
---------------------------
*
23
*
13
*
31
*
9
---------------------------
*
42
*
20
*
35
*
18
*
52
*
24
*
48
*
11
---------------------------
*
== 二项堆ha中删除节点20:
---------------------------
*
23
*
13
*
31
*
9
---------------------------
*
52
*
24
*
48
*
11
*
42
*
18
*
35
*
6
---------------------------
*
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com