长湖南营销型网站,wordpress vs,价格低文案,怎么把自己做的网站发布二叉树-堆 一、堆的概念及结构1.1 堆的概念与结构1.2 堆的性质 二、堆的实现三、堆的应用1、堆排序 一、堆的概念及结构
1.1 堆的概念与结构
堆就是完全二叉树以顺序存储方式存储于一个数组中。 然后每一个根都大于它的左孩子和右孩子的堆#xff0c;我们叫做大堆#xff… 二叉树-堆 一、堆的概念及结构1.1 堆的概念与结构1.2 堆的性质 二、堆的实现三、堆的应用1、堆排序 一、堆的概念及结构
1.1 堆的概念与结构
堆就是完全二叉树以顺序存储方式存储于一个数组中。 然后每一个根都大于它的左孩子和右孩子的堆我们叫做大堆上图就是一个典型的大堆小堆就是每一个根都小于它的左孩子和右孩子的堆。 这个就是一个小堆。
1.2 堆的性质
1、堆中某个结点的值总是不大于或不小于其父结点的值 2、堆总是一棵完全二叉树
3、 这里的规律在堆的实现中会使用到希望大家可以记住。
二、堆的实现
我们这里使用的是顺序结构所以我们可以采用之前的顺序表来存储。
1、先定义一个堆
typedef int type;typedef struct Heap
{type* arr;int size;int capacity;
}HP;这一部分在之前顺序表的章节讲过所以在这里我就不多讲了。
2、堆的初始化和销毁。
void HpInit(HP* ptr)
{assert(ptr);ptr-arr NULL;ptr-capacity ptr-size 0;
}
void HpDestroy(HP* ptr)
{assert(ptr);free(ptr-arr);ptr-capacity ptr-size 0;
}3、堆的插入
插入部分跟之前一样但是我们插入后需要进行一系列操作 比如说现在我们将1插入但是我们插完1后还是小堆吗那我们是不是要让这个1向上调整啊我们的向上调整走的是下面的过程 如果孩子小于父亲孩子和父亲就交换直到父亲小于孩子小堆大堆则反过来。 代码
void swap(int* p, int* q)//交换父亲和孩子这一部分向下调整也会用到所以封装起来
{int tep *p;*p *q;*q tep;
}
void adjustUp(type* arr, int size)
{int child size - 1;//size是数组元素个数下标等于元素个数 -1int parent (child - 1) / 2;//根据上面的公式用孩子求父亲while (child 0){if (arr[parent] arr[child]){swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}elsebreak;}
}
void HpPush(HP* ptr, type x)
{assert(ptr);if (ptr-capacity ptr-size){int newcapacity ptr-capacity 0 ? 4 : 2 * ptr-capacity;type* tep (type*)realloc(ptr-arr, sizeof(type)* newcapacity);if (tep NULL){perror(realloc);return;}ptr-arr tep;ptr-capacity newcapacity;}ptr-arr[ptr-size] x;adjustUp(ptr-arr, ptr-size);
}那上面的会写了以后我们再想想我们怎样将一个数组给建成堆呢 我们是不是可以将数组一个元素一个元素的入堆每入一个元素就向上调整一次那这样我们的堆是不是就建好了。 大家可以看到我们成功的建了一个小堆。
4、堆的删除
堆的删除跟之前不太一样我们要是删除堆最后一个元素对我们的堆有影响吗 所以我们删除的是堆顶的元素在删除堆顶的元素后要保证我们还是一个大堆或者小堆。 如果我们直接删就会出现下面的情况 所以我们要先进行一步操作交换第一个元素和最后一个元素这样我们删除最后一个元素是不会影响我们的堆的次序的然后我们在进行一个向下调整在调整时我们一定要想好交换哪个孩子如果我们建的是小堆那么就交换我们小的孩子大堆就交换大的孩子。 代码
void adjustDown(type* arr, int parent, int size)
{int child parent * 2 1;while (child size){if (child 1 size arr[child] arr[child 1])//找到小的孩子{child;}if (arr[parent] arr[child]){swap(arr[parent], arr[child]);parent child;child parent * 2 1;}elsebreak;}
}
void HpPop(HP* ptr)
{assert(ptr);swap(ptr-arr[0], ptr-arr[ptr-size - 1]);ptr-size--;adjustDown(ptr-arr, 0, ptr-size);
}5、取堆顶元素
这块比较简单我就直接给代码了
type HpTop(HP* ptr)
{assert(ptr);assert(ptr-size 0);return ptr-arr[0];
}6、判空
bool HpisEmpty(HP* ptr)
{assert(ptr);return ptr-size 0;
}7、直接用顺序表建堆
上面我们是将元素放入我们的堆后再进行其他操作但实际上我们可以直接在顺序表里建堆。 这样就直接建堆了这里是将数组看做完全二叉树。
三、堆的应用
1、堆排序
堆排序就是后面我们所说的八大排序之一的堆排那这个怎么实现 堆排序走的是这样的一个过程首先先建好一个堆然后交换第一个元素和最后一个元素因为堆顶一定是我们最大或最小的元素所以最后一个元素就排好了接下来我们进行一次向下调整选出次小的在我们的堆顶然后交换堆顶与倒数第一个元素这样倒数第二个元素就排好了直到排完整个数组。 这里我排的是逆序的为什么这里是逆序的呢这是因为我们建的小堆我们选小的在我们的数组末尾那我们是不是可以总结一个规律啊 建大堆——排升序 建小堆——排逆序
2、向下调整建堆
这个算法虽然可以用但是它的效率并没有我们的向上调整建堆高所以这里我不讲。
7、TopK
上面这些完成了我们就可以简单的打印我们这里的排序了这个问题也叫做TopK问题注意的是这里并没有进行排序只是将我们有序的数给打印出来。
void test1()
{HP hp;HpInit(hp);int arr[] { 1,5,2,8,0,4,3,7 };for (int i 0; i sizeof(arr) / sizeof(int); i){HpPush(hp, arr[i]);}//可以将我们的排序打印出来但是这里并没有进行真正的排序while (!HpisEmpty(hp)){printf(%d , HpTop(hp));//取堆顶元素直到堆为空HpPop(hp);//取一个元素删除一个元素}HpDestroy(hp);
}
int main()
{test1();return 0;
}这里我写的时候元素给的比较少我们可以改一下 这里我们在数组里放了10000个元素然后我们求最小的10个这就是TopK。
总的来说这一章难度在上升大家下来多理解这里的向上调整、向下调整以及我们的排序的过程相信大家一定可以学好的。
