Binary heap and binary search tree in C++

In C programming, binary heap and binary search tree are two commonly used data structures. They have similarities, but they also have differences. This article will introduce the concepts, basic operations and application scenarios of binary heaps and binary search trees respectively.

1. Binary Heap

1.1 Concept

A binary heap is a complete binary tree that satisfies the following two properties:

1.1.1 Heap Orderliness

Heap orderliness means that in a binary heap, the value of each node is not greater (or not less than) the value of its parent node. Here we take the max heap as an example, that is, the value of the root node is the largest value in the entire tree, and the values ​​of all child nodes are less than or equal to the value of the root node.

1.1.2 Complete Binary Tree Properties

Except for the lowest layer, all other layers must be filled, and all nodes must be aligned to the left.

Here the following array is used to represent a maximum heap:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

The corresponding heap is as shown below:

16

/
14 10
/ /
8 7 9 3
/
2 4

1

1.2 Basic operations

1.2.1 Insertion operation

The operation of inserting a new element into a binary heap uses the "sift up" method Method to make adjustments:

• Insert the new element into the leftmost empty space at the bottom of the heap;
• Compare the new element with its parent node, if the value of the new element is greater than its parent node If the node is larger, swap the positions of the two, and repeat this process until the new element is no longer larger than its parent node, or reaches the top of the heap.

1.2.2 Delete operation

The operation of deleting the top element of the heap in a binary heap is adjusted by the "sift down" method:

• Exchange the top element of the heap with the rightmost element at the bottom of the heap;
• Delete the original top element of the heap;
• Add the new top element of the heap to its child nodes layer by layer Compare it, and if its value is less than the maximum value in the child node, exchange it with the maximum value in the child node, and repeat this process until heap order is satisfied.

1.3 Application Scenario

Binary heap is often used to implement priority queues and heap-based sorting algorithms, such as heap sorting, topK problem, etc.

2. Binary Search Tree

2.1 Concept

Binary Search Tree (BST) is an ordered tree that satisfies the following properties:

2.1.1 The values ​​of all nodes on the left subtree are less than the value of its root node.

2.1.2 The values ​​of all nodes on the right subtree are greater than the value of its root node.

2.1.3 The left and right subtrees are also binary search trees respectively.

Take the following tree as an example:

    6
  /   
 2     7

/
1 4 9

   /    /
  3   5 8

Then it is a binary search tree.

2.2 Basic operations

2.2.1 Search operation

The operation of finding a node in a binary search tree, its essence is to continuously compare the value of the node to be found with The size of the current node value and recursively search along the left/right subtree.

2.2.2 Insertion operation

The operation of inserting a new node in the binary search tree requires comparison starting from the root node and finding the position where it should be inserted. After insertion, it needs to satisfy Properties of binary search trees.

2.2.3 Delete operation

The operation of deleting a node in a binary search tree can be divided into three situations:

• The node to be deleted is a leaf node , just delete it directly;
• When the node to be deleted has only one child node, replace the node with its child node;
• When the node to be deleted has two child nodes, use this node The smallest node of the right subtree replaces the node, and the smallest node of the right subtree of the node is deleted.

2.3 Application scenarios

Binary search trees are often used to implement scenarios with search and insertion operations such as dictionaries and symbol tables. The search performance is related to the distribution of data.

3. Comparison between binary heaps and binary search trees

3.1 Similarities

Both binary heaps and binary search trees are binary trees and have some of the same characteristics Properties:

• The initial position of the root node can be any node;
• can be used to implement priority queue;
• The time complexity of insertion and deletion is equal is O(logn).

3.2 Differences

There are also some obvious differences between binary heaps and binary search trees:

3.2.1 Data distribution

In a binary heap, the elements are distributed among the nodes without any regularity. You only need to ensure that each node satisfies the heap order. In a binary search tree, the size of the elements has a specific sorting rule. , that is, it satisfies the property that the left is small and the right is large.

3.2.2 Minimum/maximum value access

In a binary heap, the maximum/minimum value can be accessed in O(1), that is, it is obtained in the root node, but other The time complexity of an element is O(logn); in a binary search tree, finding the minimum/maximum value requires traversing the subtree, and the time complexity is also O(logn).

3.2.3 Deletion and insertion operations

In the binary heap, each deletion and insertion operation must follow the heap order, that is, the time complexity of O(logn); while in the In a binary search tree, the time complexity of finding a node and inserting a new node is related to the height of the tree, so in the worst case the time complexity may be O(n).

3.3 Selection Suggestions

When choosing a binary heap and a binary search tree, you need to make a selection based on the specific conditions of the application scenario.

If you need to quickly obtain the minimum/maximum value and have no special requirements on the size of the elements, you can give priority to the binary heap.

If you need to quickly insert/delete elements, and the size of the elements needs to have a certain sorting rule, you can consider choosing a binary search tree.

4. Conclusion

In summary, binary heaps and binary search trees are both relatively important data structures and have their own advantages and disadvantages in different scenarios. Understanding the concepts, basic operations and application scenarios of binary heaps and binary search trees is of great significance for writing efficient programs.

The above is the detailed content of Binary heap and binary search tree in C++. For more information, please follow other related articles on the PHP Chinese website!