Data structure - heap

Posted on In

数据结构 - 堆

Implement a binary heap

  • heap is a data structure

    • 必须是一颗完全二叉树

  • heap 分类

    • max heap(大顶堆): 父亲大孩子小
    • min heap(小顶堆): 父亲小孩子大

  • heap的插入

    • heap的插入在last position
      • last postion位置的寻找: 从上到下，从坐到右
    • heap在每次插入后，都要调整，插入后和父亲比较。
      • if smaller than parent(min heap), then bubble it up.

  • heap的删除

    • remove the highest element, then put the element at last position to the top.

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

1
2
3
4
5
6
       insert(4);
       insert(10);
       insert(15);
        /   \
      /       \
remove();      insert(0);
  1. 第一步，向一棵空树中插入值为4的结点
    insert_4
  2. 第二步，向树中插入值为10的结点
    insert_10
  3. 第三步，向树中插入值为15的结点
    insert_15
  4. 移除结点
    removal
  5. 在第三步基础上插入值为0的结点
    insert_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)$。