堆和优先队列笔记

2021-08-15

数据结构就是结构定义加上结构操作：定义一种性质，并维护这种性质。

完全二叉树内容回顾

父子节点的编号存在可计算的关系，因此不需要存储边的信息
可以使用连续空间存储

堆的概念

一种基于完全二叉树的结构
大顶堆和小顶堆
- 大顶堆：任意的三元组，父节点都大于两个子节点
- 小顶堆：任意的三元组，父节点都小于两个子节点
堆适合维护集合的最值

堆的基本操作(以大顶堆为例)

尾部插入
- 比父节点大的就和父节点交换递归向上调整
- 这个过程称为SIFT-UP
头部弹出
- 用最后一个元素(叶子节点)补位递归向下调整
- 这个过程称为SIFT-DOWN

堆,优先队列和普通队列

堆是优先队列的实现方式

普通队列	优先队列
尾部入队	尾部可以插入
头部出队	头部可以弹出
先进先出	每次出队权值最大(最大/最小的元素)
数组实现	数组实现，逻辑上看成一个堆

一句话理解堆

堆适合维护：集合之最

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

勤奋的代码搬运工<br>一位刚出来实习的前端程序员<br>谢谢大家