| title | date | permalink | tags | ||
|---|---|---|---|---|---|
Blog Post number 3 |
2021-08-25 |
/posts/2021/08/bst-vs-heap/ |
|
Can't remember what's the difference between heap & BST all the sudden...
- Definition
- Big-O complexity
Binary Search Tree is a data structure that allows for fast insertion, removal, and lookup of items while offering an efficient way to iterate them in sorted order
Heap is a complete binary tree
What is a complete binary tree?
A complete binary tree is a balanced binary tree
What is a balanced binary tree?
A balanced binary tree has its left and right subtrees of every node differ in height by no more than 1
What is tree's height / depth?
The depth of a node is the number of edges from the node to tree's root node
- The root node will have a depth of 0
The height of a node is the number of edges on hte longest path from the node to a leaf
- A leaf node will have a height of 0
Lookup,insertion,removal: O(logn) since we can discard half of the tree at each step, according to the input value being greater or less than the one in the current node-
Lookup
-
Insertion
-
Traversal
O(n) --> n nodes in the tree, each one of them only visited once
-
- A Node is at level k if distance between this node and the root node is k
- Maximum possible number fo nodes at level k is 2^k
- Usually, the heap is filled from top to bottom, at each layer, it is filled from left to right.
- As we can see that heap is not sorted, we can make it sorted by removing root node from the tree n times:
- This is also called heap sort
- Time Complexity: O(nlogn)
Binary Search Tree
Heap
Left: Min-Heap (Smallest on the top)
Right: Max-Heap (Largest on the top)
主要 difference： BST 不允许 duplicates; heap 不是 sorted
