锐客网

  1. 首页 > 睿知 > it技术 > >

算法学习笔记【day3】

算法

原视频
发现一个数据结构讲挺好的数据结构与算法教程
二叉树
  1. 如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
    算法学习笔记【day3】
    文章图片
  2. 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
算法学习笔记【day3】
文章图片

  1. 任意节点的父节点的索引为（n-1）/2; 任意节点左孩子为2n + 1；右节点为2n + 2; （这个不用记啊，这个回头画个图，把索引标上，现找规律就行,记住这玩意儿有规律就行）
堆
把上图二叉树节点当成数组索引，其实数组就是一个完全二叉树，比如： 算法学习笔记【day3】
文章图片
而这个完全二叉树就是堆
  1. 大根堆：任意节点大于所有其子节点的堆 为大根堆；反之为小根堆
  2. 构建大根堆（heapInsert）:一个个把值放到堆末尾，比较他和他父亲，谁大谁在上面，重复此过程
  3. 顶部值是任意值，下面为堆进行重排（heapify）:向下根自己两个节点的最大值比较小就换下去，重复此过程
  4. 堆中间值被修改: 如果改小了往下进行heapify 改大了网上进行heapInsert
堆排序
思路： 先将数组转成大根堆（heapInsert）每次把大根堆的顶点pop出去，把堆的最小点移到头上，进行heapify
源代码
引申阅读
【算法学习笔记【day3】】数据结构：堆（Heap）

    推荐阅读


    上一篇：leetcode 128. Longest Consecutive Sequence 最长连续序列(中等)

    下一篇：彩虹女神跃长空,Go语言进阶之Go语言高性能Web框架Iris项目实战-项目入口与路由EP01