December 17, 2014 at 16:08Data Structures: 2-3 heap (2-3 heap)
The issue of an effective way to implement a priority queue with some data structure remains relevant for a long time. The answer to this question is always a kind of compromise between the amount of memory needed to store data and the time the operations on the queue work.
In computer science, heap structures are used to efficiently implement priority queues.
A heap is a specialized tree-type data structure that satisfies the heap property: if B is a descendant node of A , then key ( A ) ≥ key ( B) It follows that the element with the largest key is always the root node of the heap, so sometimes such heaps are called max heaps (as an alternative, if the comparison is turned over, the smallest element will always be the root node, such heaps are called min heaps). There are no restrictions on how many descendant nodes each heap node has, although in practice their number is usually not more than two. Heaps are critical in some efficient graph algorithms, such as Dijkstra's algorithm and pyramid sorting.
One of the most studied and well-established data structures for storing and working with priority queues are the Binary Heap and the Fibonacci Heap.. But these structures have some features.
For example, a binary heap for basic operations has a laboriousness of Θ (logn), except finding the minimum one, and merging such heaps requires linear time (!). But storing such a heap requires little memory compared to other heaps.
The Fibonacci heap has balancing when removing a node from the heap, which reduces the complexity of the basic operations. With a large number of consecutive Fibonacci addition operations, the heap grows in width and balancing occurs only during the operation of removing the minimum, therefore, the operation of obtaining the minimum may require a significant investment of time!
Tadao Takaoka took up the solution to this problem, publishing his work “2-3 heap” in 1999 ...
2-3 heap (2-3 heap) is a tree-type data structure that satisfies the heap property (min-heap, max-heap). It is an alternative to the Fibonacci heap. Consists of 2-3 trees.
The solution that 2-3 heap offers is that, unlike the Fibonacci heap, 2-3 heap performs balancing not only when deleting, but also when adding new elements, reducing the computational load when extracting the minimum node from the heap.
The number of children of a vertex t of an arbitrary tree T is called the degree of this vertex, and the degree of its root is the degree of the tree.
2-3 trees are trees T 0 , T 1 , T 2 , ... defined inductively. Tree T 0consists of a single top. The tree T i means a tree made up of either two trees T i-1 or of three: in this case, the root of each following becomes the right-most child of the root of the previous one.
Trees 2-3 heaps are called trees H [ i ]. The tree H [ i ] is either an empty 2-3 tree, or one or two 2-3 trees of degree i connected similarly to the trees T i .
2-3 heap is an array of trees H [ i ] ( i = 0..n), for each of which the heap property is satisfied.
fig. Visual representation of heap
The smallest heap element is at the root of one of the heap trees. To find the minimum node, you need to walk through the trees.
By maintaining a pointer to the minimum node in the heap, we can find this node in constant time (Θ (1))
fig. Animation of sequentially adding items in a 2-3 pile
The minimum heap element is located at the root of one of the heap trees, let's say in H [ i ] - we will find it using FindMin. We extract the tree H [ i ] from the heap and delete its root, and the tree will decompose into subtrees, which we will add to the heap later.
We will delete the root recursively: if the tree consists of one vertex, then simply delete it; otherwise, disconnect from the root of the right-most child and continue the removal.
First of all, we can freely reduce the key at the required node. After this, you need to check: if the node is located in the root of the tree, then you do not need to do anything else, otherwise you will need to extract this node with all subtrees and insert it back into the heap (with the key already changed).
There are two heaps that need to be combined into one. To do this, we will take turns we extract all 2-3 trees from the second heap and insert them into the first heap. After that, you will need to correct the counter of the number of nodes: add the number of elements in the first and second heap and write the result into the counter in the first heap, and set the counter to 0 in the second heap.
The table shows the complexity of queue operations with priority (in the worst case, worst case)
The symbol * indicates the amortized complexity of operations
Thank you for your attention!
The source code for a C ++ implementation based on an article by 2-3 Heap is available on GitHub under MIT.
PS: When writing a course project on this topic, I realized that there is practically no information on Runet, so I decided to add my own few cents to this matter, telling the interested community about this algorithm.
In computer science, heap structures are used to efficiently implement priority queues.
A heap is a specialized tree-type data structure that satisfies the heap property: if B is a descendant node of A , then key ( A ) ≥ key ( B) It follows that the element with the largest key is always the root node of the heap, so sometimes such heaps are called max heaps (as an alternative, if the comparison is turned over, the smallest element will always be the root node, such heaps are called min heaps). There are no restrictions on how many descendant nodes each heap node has, although in practice their number is usually not more than two. Heaps are critical in some efficient graph algorithms, such as Dijkstra's algorithm and pyramid sorting.
One of the most studied and well-established data structures for storing and working with priority queues are the Binary Heap and the Fibonacci Heap.. But these structures have some features.
For example, a binary heap for basic operations has a laboriousness of Θ (logn), except finding the minimum one, and merging such heaps requires linear time (!). But storing such a heap requires little memory compared to other heaps.
The Fibonacci heap has balancing when removing a node from the heap, which reduces the complexity of the basic operations. With a large number of consecutive Fibonacci addition operations, the heap grows in width and balancing occurs only during the operation of removing the minimum, therefore, the operation of obtaining the minimum may require a significant investment of time!
Tadao Takaoka took up the solution to this problem, publishing his work “2-3 heap” in 1999 ...
A little bit about the structure of “2-3 Heap”
2-3 heap (2-3 heap) is a tree-type data structure that satisfies the heap property (min-heap, max-heap). It is an alternative to the Fibonacci heap. Consists of 2-3 trees.
The solution that 2-3 heap offers is that, unlike the Fibonacci heap, 2-3 heap performs balancing not only when deleting, but also when adding new elements, reducing the computational load when extracting the minimum node from the heap.
The number of children of a vertex t of an arbitrary tree T is called the degree of this vertex, and the degree of its root is the degree of the tree.
2-3 trees are trees T 0 , T 1 , T 2 , ... defined inductively. Tree T 0consists of a single top. The tree T i means a tree made up of either two trees T i-1 or of three: in this case, the root of each following becomes the right-most child of the root of the previous one.
Trees 2-3 heaps are called trees H [ i ]. The tree H [ i ] is either an empty 2-3 tree, or one or two 2-3 trees of degree i connected similarly to the trees T i .
2-3 heap is an array of trees H [ i ] ( i = 0..n), for each of which the heap property is satisfied.
fig. Visual representation of heap
Node structure
 | Each node has pointers to other nodes (fields with arrows), service fields and a key / priority pair (priority) - value. |
Basic operations
Finding the minimum in 2-3 heap (FindMin)
The smallest heap element is at the root of one of the heap trees. To find the minimum node, you need to walk through the trees.
By maintaining a pointer to the minimum node in the heap, we can find this node in constant time (Θ (1))
Insert in 2-3 heap (Insert)
- To add a new element, create a tree H [0] containing one vertex
- Let's perform the operation of adding this tree to the heap. When adding a tree of degree i to the heap, the following options are possible:
- If there is no tree with this priority, then just add it to the heap.
- Otherwise, we extract such a tree from the heap and connect it with the one being added, after which we add the resulting tree to the heap
- After adding, we fix the pointer to the minimum root
fig. Animation of sequentially adding items in a 2-3 pile
Removing the minimum item from the heap
The minimum heap element is located at the root of one of the heap trees, let's say in H [ i ] - we will find it using FindMin. We extract the tree H [ i ] from the heap and delete its root, and the tree will decompose into subtrees, which we will add to the heap later.
We will delete the root recursively: if the tree consists of one vertex, then simply delete it; otherwise, disconnect from the root of the right-most child and continue the removal.
Decreasing the key for an item
First of all, we can freely reduce the key at the required node. After this, you need to check: if the node is located in the root of the tree, then you do not need to do anything else, otherwise you will need to extract this node with all subtrees and insert it back into the heap (with the key already changed).
Combining two heaps into one
There are two heaps that need to be combined into one. To do this, we will take turns we extract all 2-3 trees from the second heap and insert them into the first heap. After that, you will need to correct the counter of the number of nodes: add the number of elements in the first and second heap and write the result into the counter in the first heap, and set the counter to 0 in the second heap.
Comparison of the complexity of operations with other algorithms
The table shows the complexity of queue operations with priority (in the worst case, worst case)
The symbol * indicates the amortized complexity of operations
| Operation | Binary heap | Binomial heap | Fibonacci heap | 2-3 Heap |
|---|---|---|---|---|
| Findmin | Θ (1) | O (logn) | Θ (1) * | Θ (1) * |
| Deletemin | Θ (logn) | Θ (logn) | O (logn) * | O (logn) * |
| Insert | Θ (logn) | O (logn) | Θ (1) * | Θ (1) * |
| Decreasekey | Θ (logn) | Θ (logn) | Θ (1) * | Θ (1) * |
| Merge / union | Θ (n) | Ω (logn) | Θ (1) | Θ (1) * |
Thank you for your attention!
The source code for a C ++ implementation based on an article by 2-3 Heap is available on GitHub under MIT.
PS: When writing a course project on this topic, I realized that there is practically no information on Runet, so I decided to add my own few cents to this matter, telling the interested community about this algorithm.
