AI 助理
备案控制台
开发者社区 人工智能 文章 正文

STL和优先队列

2023-11-01 36
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： STL和优先队列

学习目标：

优先队列也是一种抽象数据类型。优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。

也就是说优先队列，通常会有下面的操作：

  • 将元素插入队列
  • 将最大或者最小元素删除

这样的话，我们完全可以使用链表来实现，例如以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;
  };
}
文章标签：
C++
算法
乖的小肥羊
目录
相关文章
泡沫o0
|
6月前
|
算法 数据处理 调度
【C++ 优先队列】了解 C++优先队列中操作符重载的实现
【C++ 优先队列】了解 C++优先队列中操作符重载的实现
泡沫o0
89 0
我菜就爱学
|
6月前
|
C++ 容器
STL—map容器
STL—map容器
我菜就爱学
34 0
北飞的山羊
|
6月前
|
存储 C++ 容器
C++之STL顺序容器
C++之STL顺序容器
北飞的山羊
35 0
aliyun_11084
|
算法 安全 搜索推荐
7.1 C++ STL 非变易查找算法
C++ STL 中的非变易算法（Non-modifying Algorithms）是指那些不会修改容器内容的算法，是C++提供的一组模板函数，该系列函数不会修改原序列中的数据，而是对数据进行处理、查找、计算等操作，并通过迭代器实现了对序列元素的遍历与访问。由于迭代器与算法是解耦的，因此非变易算法可以广泛地应用于各种容器上，提供了极高的通用性和灵活性。
aliyun_11084
47 0
北海。
|
6月前
|
存储 C++ 容器
C++ STL学习之【优先级队列】
C++ STL学习之【优先级队列】
北海。
67 0
干饭小白
|
容器
STL-deque
STL-deque
干饭小白
41 0
Dio夹心小面包
|
存储 C++ 容器
『C++之STL』双端队列 - deque
『C++之STL』双端队列 - deque
Dio夹心小面包
116 0
Fox!
|
存储 算法 C++
【C++：STL之栈和队列 | 模拟实现 | 优先级队列 】(二）
【C++：STL之栈和队列 | 模拟实现 | 优先级队列 】(二）
Fox!
102 0
Fox!
|
存储 编译器 C语言
【C++：STL之栈和队列 | 模拟实现 | 优先级队列 】(一）
【C++：STL之栈和队列 | 模拟实现 | 优先级队列 】(一）
Fox!
83 0
云与尘呀？
|
算法 C++ 容器
STL之队列、优先队列、栈
STL之队列、优先队列、栈
云与尘呀？
83 0