线段树


  • 线段树不是完全二叉树
  • 线段树是平衡二叉树
  • 堆也是平衡二叉树

实现

  • 如下方法

    • buidlSegment(int $treeIndex ,int $l , int $r):void 构造线段树
    • query(int $queryL, int $queryR) 查询区间范围
    • set(int $index , $e) 更新操作
  • QQ截图20181029123859.png


堆-最大堆与优先队列


简介

  • 优先队列-是队列的一种,普通队列是先入先出(lifo)而优先队列出队的顺序是根据根据优先级最高的有关系,所以跟进入的顺序没有关系了,那么有如下的解决方案和分析

    • Array 数组实现,

      • 入队 0(n)
      • 出队 O(1)
    • LinkList 链表实现

      • 入队 O(1)
      • 出队 O(N)
    • heap 堆基于array的二叉树

      • 入队 O(logn)
      • 出队 O(logn)