数据结构 - 堆

什么是堆?

todo

堆在生活中的应用

todo

实现一个二叉堆

• heap is a data structure
  • 必须是一颗完全二叉树
• 堆的分类
  • max heap(大顶堆): 父亲大孩子小
  • min heap(小顶堆): 父亲小孩子大
• 堆的插入
  • heap的插入在last position
    • last postion位置的寻找: 从上到下，从左到右
  • heap在每次插入后，都要调整，插入后和父亲比较。
    • if smaller than parent(min heap), then bubble it up.
• 堆的删除
  • remove the highest element, then put the element at last position to the top.

下边来完成一次手动模拟, 步骤如下所示:

             insert(4);
             insert(10);
             insert(15);
              /   \
            /       \
      remove();      insert(0);

1. 第一步，向一棵空树中插入值为4的结点
2. 第二步，向树中插入值为10的结点
3. 第三步，向树中插入值为15的结点
4. 移除结点
5. 在第三步基础上插入值为0的结点

Insert an element: insert into the last position and bubble it up.

Remove an element: remove the highest element and put the element at last position to the top, then bubble it down.

时间复杂度

• insert = $\color{ blue }{O(logn)}$
• removal = $\color{blue}{O(logn)}$

其实可以理解为树的高度，因为完全二叉树的高度为$\lceil{log_2(n+1)}\rceil$, 其时间复杂度可以认为是$O(log_2n)$。