一网网站制作平台,深圳珠宝品牌网站设计,哈尔滨建设集团董事长,强生公司网站建设原则堆的概念及结构 如果有一个关键码的集合K { #xff0c; #xff0c; #xff0c;…#xff0c; }#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中#xff0c;并满足#xff1a; 且 ( 且 ) i 0#xff0c;1#xff… 堆的概念及结构 如果有一个关键码的集合K { … }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 ( 且 ) i 012…则称为小堆(或大堆)。 将根节点最大的堆叫做最大堆或大根堆 节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 1.下列关键字序列为堆的是 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32 2.已知小根堆为8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是。 A 1 B 2 C 3 D 4 3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 A(11 5 7 2 3 17) B(11 5 7 2 17 3) C(17 11 7 2 3 5) D(17 11 7 5 3 2) E(17 7 11 3 5 2) F(17 7 11 3 2 5) 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是 A[3257468] B[2357468] C[2345786] D[2345678]
选择题答案
1.A 2.C 3.C 4.C
堆的实现
1 堆向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37}; 堆的创建 下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢
在此我们有两种建堆方法 1. 利用向上调整的方法从第2 个节点开始一直调整到最后就可以调整成堆。 2. 利用向下调整的方法我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。
但是第一种建堆的时间复杂度为 O(N*logN)第二种建堆的时间复杂度为O(N)
所以我们在此用第二种方法。 堆的插入 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 堆的删除 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 堆的代码实现
Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestring.htypedef int HeapDataType;
typedef struct Heap
{HeapDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* ph);void HeapInitArray(HeapDataType* a, Heap* ph,int n);
void HeapDestroy(Heap* ph);
void HeapPush(Heap* ph, HeapDataType x);
void HeapPop(Heap* ph);
HeapDataType HeapTop(Heap* ph);
void AdjustUp(HeapDataType* a, int child);
void AdjustDown(HeapDataType* pa, int n, int parent);
bool HeapEmpty(Heap* ph);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.hvoid HeapInit(Heap* ph)
{assert(ph);ph-a NULL;ph-size 0;ph-capacity 0;
}
void HeapDestroy(Heap* ph)
{assert(ph);ph-size 0;ph-capacity 0;free(ph-a);ph-a NULL;
}//利用其它数组数据建造一个堆存储数据
void HeapInitArray(Heap* ph,HeapDataType* a, int n)
{assert(ph);HeapDataType* tmp (HeapDataType*)malloc(sizeof(HeapDataType) * n);if (tmp NULL){perror(malloc fail!);exit(-1);}ph-a tmp;ph-size ph-capacity n;memcpy(ph-a , a , n*sizeof(HeapDataType));//向上调整建堆时间复杂度ON*logN//for (int i 1; i ph-size; i)//{// AdjustUp(ph-a,i);//}//向下调整建堆从第一个不为叶子的节点时间复杂度ONfor(int i (ph-size - 1 - 1)/2; i 0; i--){AdjustDown(ph-a,n,i);}
}void Swap(HeapDataType*p1, HeapDataType*p2)
{HeapDataType tmp*p1;*p1 *p2;*p2 tmp;
}void AdjustDown(HeapDataType* a,int n , int parent)
{int child parent*2 1;while (child n){if (child 1n a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent],a[child]);parent child;child parent * 2 1;}else{break;}}
}
//建造小堆
void AdjustUp(HeapDataType* a, int child)
{int parent (child - 1) / 2;//while(parent0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void HeapPush(Heap* ph, HeapDataType x)
{assert(ph);if (ph-size ph-capacity){int newcapacity ph-capacity 0 ? 4 : ph-capacity * 2;HeapDataType* tmp(HeapDataType*)realloc(ph-a,newcapacity*sizeof(HeapDataType));if (tmp NULL){perror(realloc fail!);exit(-1);}ph-a tmp;ph-capacity newcapacity;}ph-size;ph-a[ph-size - 1] x;AdjustUp(ph-a, ph-size - 1);
}
void HeapPop(Heap* ph)
{assert(ph);//必须有数据assert(ph-size);Swap(ph-a[0], ph-a[ph-size - 1]);ph-size--;AdjustDown(ph-a,ph-size,0);}
HeapDataType HeapTop(Heap* ph)
{assert(ph);return ph-a[0];
}
bool HeapEmpty(Heap* ph)
{assert(ph);return ph-size 0;
}
Test.c
#includeHeap.h
int main()
{//Heap heap1;//HeapInit(heap1);//HeapPush(heap1,1);//HeapPush(heap1,54);//HeapPush(heap1,48);//HeapPush(heap1,48);//HeapPush(heap1,15);//HeapPush(heap1,35);//int a []{21,54,87,64,87,15};//Heap heap2;//HeapInit(heap2);//for (int i 0; i (sizeof(a)/sizeof(int)); i)//{// HeapPush(heap2, a[i]);//}//while (!HeapEmpty(heap2))//{// printf(%d\n, HeapTop(heap2));// HeapPop(heap2);//}//int a[] { 21,54,87,64,87,15 };//Heap heap2;//HeapInitArray(heap2 ,a,sizeof(a)/sizeof(HeapDataType));//建立了小堆//HeapDestroy(heap2);return 0;
} 这个博客如果对你有帮助给博主一个免费的点赞就是最大的帮助❤
欢迎各位点赞收藏和关注哦❤
如果有疑问或有不同见解欢迎在评论区留言哦❤
后续我会一直分享双一流211西北大学软件C数据结构CLinuxMySQL的学习干货以及重要代码的分享
