数据结构—堆的基本操作(c语言实现）

1.基本函数实现

a.代码1(向下调整)

void AdjustDown(DateType*a, int n, int parent)
{int child &＃61; parent * 2 &＃43; 1;while (child a[child &＃43; 1]){&＃43;&＃43;child;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent &＃61; child;child &＃61; parent * 2 &＃43; 1;}else{break;}}
}

注意:if里面的条件语句(child &＃43;1)

b.代码2(向上调整)

void AdjustUp(DateType*a , int child)
{int parent &＃61; (child - 1) / 2;while (child > 0){if (a[child] }

注意:while里面的条件语句是不能够写成(parent<0)&＃xff0c;因为当child&＃61;&＃61;0时&＃xff0c;parent&＃61;(child - 1) / 2,parent&＃61;&＃61;0,再次进入循环不满足a[child]

c.代码3(交换&＃xff09;

void Swap(DateType*p1, DateType*p2)
{DateType tmp &＃61; *p1;*p1 &＃61; *p2;*p2 &＃61; tmp;
}

2.建堆 

void CreatHeap(Heap*p,DateType*num,int n)
{assert(p);p->a &＃61; (DateType*)malloc(n * sizeof(DateType));if (p->a &＃61;&＃61; NULL){printf("malloc failed\n");exit(-1);}memcpy(p->a, num, n * sizeof(DateType));p->size &＃61; n;p->capacity &＃61; n;//建小堆for (int i &＃61; (n - 1 - 1) / 2; i >&＃61; 0; i--){AdjustDown(p->a, p->size, i);}
}

3.插入数据

void HeapPush(Heap*p, DateType x)
{assert(p);if (p->size &＃61;&＃61; p->capacity){DateType*tmp &＃61; (DateType*)realloc(p->a, (p->capacity) * 2 * sizeof(DateType));if (tmp &＃61;&＃61; NULL){printf("realloc failed\n ");exit(-1);}}(p->capacity) *&＃61; 2;p->a[p->size] &＃61; x;&＃43;&＃43;(p->size);//向上调整AdjustUp(p->a, p->size-1);
}

4. 删除数据

void HeapPop(Heap*p, DateType x)
{assert(p);Swap(&p->a[0], &p->a[p->size-1]);--(p->size);AdjustDown(p->a, p->size, 0);//左右子树还是小堆&＃xff0c;直接调整行了
}

把堆顶的数据与最后一个数据交换&＃xff0c;再次调整size-1个数据。 

5.获取堆顶的数据

DateType HeapTop(Heap*p)
{assert(p);return p->a[0];
}

6.堆的数据个数

int HeapSize(Heap*p)
{assert(p);return p->size;
}

7.判空

bool HeapIsEmpty(Heap*p)
{assert(p);return p->size &＃61;&＃61; 0;
}

8.打印

void Print(Heap*p)
{assert(p);for (int i &＃61; 0; i size; i&＃43;&＃43;){printf("%d ", (p->a)[i]);}printf("\n");int count &＃61; 0;//计数int levelsize &＃61; 1;for (int i &＃61; 0; i size; i&＃43;&＃43;){printf("%d ", p->a[i]);&＃43;&＃43;count;if (count &＃61;&＃61; levelsize){printf("\n");levelsize *&＃61; 2;count &＃61; 0;//重新计数}}printf("\n");
}

8.销毁

void HeapDestory(Heap*p)
{assert(p);free(p->a);p->a &＃61; NULL;p->capacity &＃61; p->size &＃61; 0;
}

9.测试

int main()
{int num[] &＃61; { 12,15,17,23,10,25 };int n &＃61; sizeof(num) / sizeof(num[0]);Heap a;//创建小堆CreatHeap(&a,num, n);Print(&a);printf("\n");//插入数据HeapPush(&a, 1);Print(&a);//删除对顶的数据HeapPop(&a);Print(&a);printf("\n");//获取堆顶数据int ret&＃61;HeapTop(&a);printf("The top date is %d\n",ret);//堆的数据个数int number&＃61;HeapSize(&a);printf("The number of heap is %d\n", number);//销毁HeapDestory(&a);return 0;
}

10.测试结果

11.用堆排序(降序)

a.代码1

int main()
{DateType num[] &＃61; { 12,15,17,23,10,25 };int n &＃61; sizeof(num) / sizeof(num[0]);HeapSort(num, n);for (int i &＃61; 0; i }

void HeapSort(int*num, int n)
{//建小堆for (int i &＃61; (n - 1 - 1) / 2; i >&＃61; 0; i--){AdjustDown(num, n, i);}int end &＃61; n - 1;while (end>0){Swap(&num[0], &num[end]);AdjustDown(num, end, 0);--end;}
}

运行结果

堆的基本操作今天就分享在到这里了&＃xff0c;谢谢你的浏览&＃xff0c;如果对你有帮助的话&＃xff0c;可以点一个赞&＃xff0c;随便来个关注。