Heap

05 Jan 2022 . data structure .

  • Max-Heap:
    • In a Max-Heap the data element present at the root node must be the greatest among all the data elements present in the tree.
    • This property should be recursively true for all sub-trees of that binary tree.
  • Min-Heap:
    • In a Min-Heap the data element present at the root node must be the smallest (or minimum) among all the data elements present in the tree.
    • This property should be recursively true for all sub-trees of that binary tree.

Time Complexity

  • Build heap：O（nlog n）
  • Max/Min value：O（1）
  • Insert/Delete：O（n）