学习目标：
优先队列也是一种抽象数据类型。优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。
也就是说优先队列，通常会有下面的操作：
- 将元素插入队列
- 将最大或者最小元素删除
这样的话，我们完全可以使用链表来实现，例如以O（1）复杂度插入，每次在表头插入，而以O（N）复杂度执行删除最小元素；或者以O（N）复杂度插入，保持链表有序，而以O（1）复杂度删除。
优先队列的底层是一个二叉堆的数据结构
1.理解什么是优先队列
2.有哪些核心点
核心在调整算法和删除那里
调整算法细节写在代码里
删除我们可以理解为我们想要杀第一个人，不能太显眼，那么就把第一个人与最后一个换
位置，那么再去杀他，就不会被人发现了
下面图示是建堆算法
#pragma once #include <stdio.h> #include <stdlib.h> //先构造大堆 #include <assert.h> #include <string.h> typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; int c = 7; int* s = &c; //向上调整算法 void AdjustUp(HPDataType* Up, int child);//我们得知道插入的位置在哪我们才能调整 //需要自定义一个向上调整算法 //向上调整算法可以建堆 void AdjustUp(HPDataType* Up, int child)//跟老师的思路一样,没问题 { int tmp = 0; int parents = (child - 1) / 2;//这样插入的前提是本身他就是个堆我们才能这么插入 while (child) { parents = (child - 1) / 2; if (Up[parents] < Up[child]) { tmp = Up[child]; Up[child] = Up[parents]; Up[parents] = tmp; child = parents; } else { break; } } } void AdjustDown(HPDataType* a, int n, int parents);//向下调整算法,可以用于删除数据 //因为我们删除数据的原理是队头数据和队尾部数据交换，然后队尾-1 //再开始执行向下调整算法(那此时这里我们有几个要注意的点就是——我们如果直接删除队头数据的话 //我们可能会打乱堆里面的整体数据顺序，而为了不打乱整体的数据顺序，所以我们 //采用交换位置的方法),然后执行向下调整算法 void AdjustDown(HPDataType* a, int n, int parents) { //向下调整算法里我们得知道他的父节点，再开始进行向下调整 //而在向下调整的时候,我们得判断两边哪个最大，我们挑最大的上场，然后在他的路径下一直判断 //挑最大的上来能保证第一行是最大的 //因为根据我们的前面的推论左右孩子永远比父节点小 //所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面 //这里我们不用定义leftchild和rightchild，而是我们 //用一种很独特的方式 //假设定义法，我们直接去把定义一个孩子定义为最大的 //已知左孩子公式为 2*parents+1 //这里我们假设左孩子为最大 int tmp = 0;//交换的容器 int child = 2 * parents + 1; while (child < n)//迭代过程，停止条件,也不能child-1<n //是因为我们如果child-1<n的话,如果我们的child下标时的数据<child+1时下标数据时，我们就没有去判断了 //也就是当我们最后child下标为最后一个时，我们就少判断了一次，所以我们需要再去判断一次 { //那么也就是如果child 下标小于child+1时，我们就加个条件child+1<n限制再执行child++。 //这是为了以防越界， if (a[child] > a[child+1] && child+1<n)//先判断左右孩子哪个大，如果假设的孩子小，那么就++下标 //其实就是左孩子小于右孩子，那么下标就跳到右孩子这里 //思考为什么要加child+1<n呢，是因为我们最后child赋值后大于n的情况有三种 //一种是赋值后在最后一个下标，，一种是赋值之后在我们给定的下标外面（这个我们已经确定好条件了 // 就是我们child<n） //但是我们每次迭代后又要判断 { ++child; } if (a[parents] > a[child]) { tmp = a[parents]; a[parents] = a[child]; a[child] = tmp; parents = child; child = 2 * parents + 1; } else { break; } } } void AdjustDown1(HPDataType* a, int n, int parents);//向下调整算法,可以用于删除数据 //因为我们删除数据的原理是队头数据和队尾部数据交换，然后队尾-1 //再开始执行向下调整算法(那此时这里我们有几个要注意的点就是——我们如果直接删除队头数据的话 //我们可能会打乱堆里面的整体数据顺序，而为了不打乱整体的数据顺序，所以我们 //采用交换位置的方法),然后执行向下调整算法 void AdjustDown1(HPDataType* a, int n, int parents)//调整数组里的值,小根堆 { //向下调整算法里我们得知道他的父节点，再开始进行向下调整 //而在向下调整的时候,我们得判断两边哪个最大，我们挑最大的上场，然后在他的路径下一直判断 //挑最大的上来能保证第一行是最大的 //因为根据我们的前面的推论左右孩子永远比父节点小 //所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面 //这里我们不用定义leftchild和rightchild，而是我们 //用一种很独特的方式 //假设定义法，我们直接去把定义一个孩子定义为最大的 //已知左孩子公式为 2*parents+1 //这里我们假设左孩子为最大 int tmp = 0;//交换的容器 int child = 2 * parents + 2; while (child-1 < n)//迭代过程，停止条件 { if (a[child] > a[child-1])//先判断左右孩子哪个大，如果假设的孩子小，那么就++下标 //其实就是左孩子小于右孩子，那么下标就跳到右孩子这里 { child--; } if (a[parents] < a[child]) { break; } else { tmp = a[parents]; a[parents] = a[child]; a[child] = tmp; parents = child; child = 2 * parents + 1; } } } // 堆的构建 void HeapCreate(Heap* hp, HPDataType* a, int n); void HeapCreate(Heap* hp, HPDataType* a, int n) { hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n); hp->_capacity = n; hp->_size = n; if (hp->_a == NULL) { perror("malloc fail\n"); exit(-1); } int i = 0; //while (i<n)//这样构建效率很低 //{ // HeapPush(hp, a[i]); // i++; //} for (int i = (n - 1 - 1) / 2; i >= 0; --i)//修改数组的值，我们利用堆进行 { AdjustDown(a, n, i); } memcpy(hp->_a, a, sizeof(HPDataType) * n);//用内存函数去把数组这些里面的内存拷贝到hp_a // 建堆算法 } void swap(Heap* hp);//删除的时候为了不改变顺序而交换 void swap(Heap* hp) { assert(hp); assert(hp->_size > 0); int tmp = 0; tmp = hp->_a[0]; hp->_a[0] = hp->_a[hp->_size - 1]; hp->_a[hp->_size - 1] = tmp; return; } // 堆的销毁 void HeapDestory(Heap* hp); void HeapDestory(Heap* hp) { hp->_size = hp->_capacity = 0; free(hp->_a); free(hp); } // 堆的插入 //我们把堆看成一个完全二叉树，每次的插入必定有一个父节点 //1.所以我们可以根据堆的父节点公式推出父节点，并且我们现在实现的是大堆，所以每次插入时要去比对 //堆的插入是 void HeapPush(Heap* hp, HPDataType x); void HeapPush(Heap* hp, HPDataType x)//这里我们只需要调整一条祖先路径就行 //我们的堆不是栈，我们的堆只要确保他的父节点比他的孩子节点大就行//没问题 { //第一种方法 if (hp->_capacity == hp->_size) { ++hp->_capacity; HPDataType* ptr = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity); if (ptr == NULL) { perror(" malloc fail "); exit(-1); } hp->_a = ptr; } int child = hp->_size; hp->_a[hp->_size++] = x; AdjustUp(hp->_a,child); } // 堆的删除 void HeapPop(Heap* hp);//删除之后要维持这个大根堆 //堆的删除要注意，是因为我们如果直接删除堆顶的话 //那么我们可能就会所有节点的顺序就会变了 //所以堆的删除我们可以最后一个和第一个互换位置 //然后size--，我们在看看交换后是不是比他左右孩子大 //如果不是就挑最大的上来,挑最大的上来能保证第一行是最大的 //因为根据我们的前面的推论左右孩子永远比父节点小 //所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面 void HeapPop(Heap* hp) { assert(hp); assert(hp->_size > 0); swap(hp); //此时是我们已知父亲节点 //求孩子节点 //求孩子节点的公式就是 //int child = 0; //int parents = 0; //int tmp = 0; //int leftchild = 2 * parents + 1; //int rightchild = 2 * parents + 2; //while ((leftchild = 2 * parents + 1) < hp->_size - 1 && (rightchild = 2 * parents + 2) < hp->_size - 1)//想一想我们应该以什么截止呢，是child还是parents //{ // /*leftchild = 2 * parents + 1; // rightchild = 2 * parents + 2;*/ // if (hp->_a[parents] >= hp->_a[rightchild] && hp->_a[parents] < hp->_a[leftchild]) // { // tmp = hp->_a[leftchild]; // hp->_a[leftchild] = hp->_a[parents]; // hp->_a[parents] = tmp; // parents = leftchild; // } // else if (hp->_a[parents] < hp->_a[rightchild] && hp->_a[parents] >= hp->_a[leftchild]) // { // tmp = hp->_a[rightchild]; // hp->_a[rightchild] = hp->_a[parents]; // hp->_a[parents] = tmp; // parents = rightchild; // } // else if (hp->_a[parents] < hp->_a[rightchild] && hp->_a[parents] < hp->_a[leftchild]) // { // if (hp->_a[rightchild] >= hp->_a[leftchild]) // { // tmp = hp->_a[rightchild]; // hp->_a[rightchild] = hp->_a[parents]; // hp->_a[parents] = tmp; // parents = rightchild; // } // else // { // tmp = hp->_a[leftchild]; // hp->_a[leftchild] = hp->_a[parents]; // hp->_a[parents] = tmp; // parents = leftchild; // } // } // else // { // break; // } //} hp->_size--; int parents = 0; AdjustDown(hp->_a, hp->_size, parents); } // 取堆顶的数据 HPDataType HeapTop(Heap* hp); HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->_size > 0); return hp->_a[0]; } // 堆的数据个数 int HeapSize(Heap* hp); int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 堆的判空 int HeapEmpty(Heap* hp); int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; } void Print(Heap* h1); void Print(Heap* h1) { for (int i=0;i<h1->_size;i++) { printf("%d ", h1->_a[i]); } printf("\n"); } // TopK问题：找出N个数里面最大/最小的前K个问题。 // 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题， // 需要注意： // 找最大的前K个，建立K个数的小堆 // 找最小的前K个，建立K个数的大堆 //我这里是大根堆，所以我们第一个父节点永远是最大的 //可能左节点的孩子比右节点大，可能右节点的孩子比左节点大，但是他们都比自身的父节点小 //他们的父节点又比自身的父节点小，所以层层从下往上推，第一个父节点肯定是最大的 void PrintTopK(int* a, int n, int k, Heap* h1); void PrintTopK(int* a, int n, int k, Heap* h1) { assert(h1->_size >= k); while (k--) { printf("%d ", HeapTop(h1)); HeapPop(h1); } } //void PrintTopK1(int* a, int n, int k, Heap* h1); //void PrintTopK1(int* a, int n, int k, Heap* h1) //{ // assert(h1->_size >= k); // while (k--) // { // printf("%d ",HeapTop(h1)); // HeapPop(h1); // } //} void Swap(int* S1, int* S2); void Swap(int* S1, int* S2) { int tmp = 0; tmp = *S1; *S1 = *S2; *S2 = tmp; } void HeapAscrSort(int* Sort, int n,int parents); void HeapAscrSort(int* Sort, int n,int parents) { int i = n; for (int i = (n-2)/2;i>=0;i--) { AdjustDown(Sort, n, i); } int End =n-1; while (End>0) { Swap(&Sort[0], &Sort[End]); AdjustDown(Sort, End, parents); End--; } }
STL源码
1.学习适配器和仿函数
那什么是适配器呢？
就像我们生活中使用的电源适配器一样，已经有的接口是家里的插口，它是220V的，而我们经常使用的电子设备用到的电压远没有这么高，所以就需要将电压进行转换，转换成我们能用的低电压。
比如手机充电器，它就将220V电压转换到了手机能承受的低电压。
那什么是仿函数呢
仿函数其实是一个类，只不过这个类可以向函数一样去调用
如果不用仿函数的话，那么我们调用函数的话，需要传函数指针进行调用
因为函数指针用起来很复杂(不知道函数指针的可以搜一搜函数指针),所以C++要用
仿函数
#include <iostream> #include <algorithm> #include <cstring> #include <vector> //stack使用其他容器进行封装的数据结构 //因为stack只有尾插和尾删，我们可以采用 //deque的容器进行封装 //我们这里用到的Container就是一个适配器 namespace txh { template<class T> class greater { public: bool operator()(const T& x,const T& y) { return x > y; } }; template<class T> class less { public: bool operator()(const T& x, const T& y)//仿函数 //是一个类，只不过这个类可以和函数一样可以直接调用 { return x < y; } }; template<class T, class Container = std::vector<T>, class Comapre = less<T>> class priority_queue { public: priority_queue() { } void adjust_up(size_t child) { Comapre com; size_t parent = (child - 1) / 2; while (child > 0) { if ((com(_con[parent], _con[child]))) { std::swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent) { Comapre com; size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child], _con[child + 1] )) { child++; } if (com(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else break; } } void push(const T& val) { _con.push_back(val); adjust_up(_con.size() - 1); } void pop() { if (empty()) return; std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; }
