Is a binary search tree a special case of a binary max
As far as I understand, in a max-heap the value of each node is greater than or equal to all of it's children. The same applies for a binary search tree, but in this data structure it's also important that nodes on the same level (siblings) are structured correctly.
This made me think that a binary search tree is basically a max-heap with an extra property. So every BST is also a max-heap. Am I right?
No; in a BST, the root is no greater than anything in the left subtree, but no smaller than anything in the right. As you say, the root in a max heap is greater than anything in both subtree. So you could say a BST has an extra property, but that very property makes it not a max heap.
No.
Structural Difference
Basically, tree and heap differs by their structures. A binary search tree is still a tree, and so any node can have less than 2 children. But a max heap is still a heap, and so only the penultimate level's nodes can have less than 2 children.
Getting sorted list of Elements
BST -> O(N) = by traversing in a recursive manner.
Max Heap -> O(N Log N) = by removing max value in root for N times, each operation takes O(Log N) time
Parent-Children Relationship
BST is a tree data structure, which possesses a relationship between Parent and Children and between the Children. But, heap possesses only the relationship between Parent and Children and not between the Children.
If you need comparison, you could think of Binary max Heap as an extension of "Complete" Binary tree ( not complete BST! ), with each node having all children lesser than itself (As explained here)
Binary heap is a special case of a binary tree (But not the BINARY SEARCH tree!), but not the opposite. Binary heap is a binary tree with the shape and heap property: It is a COMPLETE tree, with all of the level fully populated except the last one, and all nodes are greater(less) than or equal to each of its children.
链接地址: http://www.djcxy.com/p/82826.html上一篇: 这堆实际上是一堆吗？
下一篇: 二叉搜索树是二进制最大值的特例