Un montón sesgado (o montón autoajustable) es una estructura de datos de montón implementada como un árbol binario . Los montones sesgados son ventajosos debido a su capacidad para fusionarse más rápidamente que los montones binarios. A diferencia de los montones binarios , no hay restricciones estructurales, por lo que no hay garantía de que la altura del árbol sea logarítmica. Solo se deben cumplir dos condiciones:
- El orden general del almacenamiento dinámico debe estar allí (la raíz es mínima y lo mismo se cumple recursivamente para los subárboles), pero no se requiere la propiedad equilibrada (todos los niveles deben estar llenos excepto el último).
- La operación principal en Skew Heaps es Merge. Podemos implementar otras operaciones como insert, extractMin(), etc. usando solo Merge.
Ejemplo:
1. Considere que el montón sesgado 1 es
2. El segundo montón a considerar
4. Y obtenemos el árbol fusionado final como
Proceso de fusión recursivo:
fusionar (h1, h2)
- Sean h1 y h2 los montones sesgados de dos minutos que se fusionarán. Deje que la raíz de h1 sea más pequeña que la raíz de h2 (si no es más pequeña, podemos intercambiar para obtener la misma).
- Intercambiamos h1->izquierda y h1->derecha.
- h1->izquierda = fusionar(h2, h1->izquierda)
Ejemplos:
Let h1 be
10
/ \
20 30
/ /
40 50
Let h2 be
15
/ \
25 35
/ \
45 55
After swapping h1->left and h1->right, we get
10
/ \
30 20
/ /
50 40
Now we recursively Merge
30
/ AND
50
15
/ \
25 35
/ \
45 55
After recursive merge, we get (Please do it
using pen and paper).
15
/ \
30 25
/ \ / \
35 50 45 55
We make this merged tree as left of original
h1 and we get following result.
10
/ \
15 20
/ \ /
30 25 40
/ \ / \
35 40 45 55
Para visualización: https://www.cs.usfca.edu/~galles/JavascriptVisual/LeftistHeap.html
CPP
// CPP program to implement Skew Heap
// operations.
#include <bits/stdc++.h>
using namespace std;
struct SkewHeap
{
int key;
SkewHeap* right;
SkewHeap* left;
// constructor to make a new
// node of heap
SkewHeap()
{
key = 0;
right = NULL;
left = NULL;
}
// the special merge function that's
// used in most of the other operations
// also
SkewHeap* merge(SkewHeap* h1, SkewHeap* h2)
{
// If one of the heaps is empty
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;
// Make sure that h1 has smaller
// key.
if (h1->key > h2->key)
swap(h1, h2);
// Swap h1->left and h1->right
swap(h1->left, h1->right);
// Merge h2 and h1->left and make
// merged tree as left of h1.
h1->left = merge(h2, h1->left);
return h1;
}
// function to construct heap using
// values in the array
SkewHeap* construct(SkewHeap* root,
int heap[], int n)
{
SkewHeap* temp;
for (int i = 0; i < n; i++) {
temp = new SkewHeap;
temp->key = heap[i];
root = merge(root, temp);
}
return root;
}
// function to print the Skew Heap,
// as it is in form of a tree so we use
// tree traversal algorithms
void inorder(SkewHeap* root)
{
if (root == NULL)
return;
else {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
return;
}
};
// Driver Code
int main()
{
// Construct two heaps
SkewHeap heap, *temp1 = NULL,
*temp2 = NULL;
/*
5
/ \
/ \
10 12 */
int heap1[] = { 12, 5, 10 };
/*
3
/ \
/ \
7 8
/
/
14 */
int heap2[] = { 3, 7, 8, 14 };
int n1 = sizeof(heap1) / sizeof(heap1[0]);
int n2 = sizeof(heap2) / sizeof(heap2[0]);
temp1 = heap.construct(temp1, heap1, n1);
temp2 = heap.construct(temp2, heap2, n2);
// Merge two heaps
temp1 = heap.merge(temp1, temp2);
/*
3
/ \
/ \
5 7
/ \ /
8 10 14
/
12 */
cout << "Merged Heap is: " << endl;
heap.inorder(temp1);
}
The heap obtained after merging is: 12 8 5 10 3 14 7
Publicación traducida automáticamente
Artículo escrito por nickhilrawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA