Eliminación en montón
Dado un montón binario y un elemento presente en el montón dado. La tarea es eliminar un elemento de este Heap.
La operación de eliminación estándar en Heap es eliminar el elemento presente en el Node raíz de Heap. Es decir, si es un montón máximo, la operación de eliminación estándar eliminará el elemento máximo y si es un montón mínimo, eliminará el elemento mínimo.
Proceso de eliminación :
dado que eliminar un elemento en cualquier posición intermedia en el montón puede ser costoso, podemos simplemente reemplazar el elemento que se eliminará por el último elemento y eliminar el último elemento del montón.
- Reemplace la raíz o el elemento a eliminar por el último elemento.
- Elimina el último elemento del Heap.
- Dado que, el último elemento ahora se coloca en la posición del Node raíz. Por lo tanto, es posible que no siga la propiedad del montón. Por lo tanto, apile el último Node colocado en la posición de raíz.
Ilustración :
Suppose the Heap is a Max-Heap as:
10
/ \
5 3
/ \
2 4
The element to be deleted is root, i.e. 10.
Process:
The last element is 4.
Step 1: Replace the last element with root, and delete it.
4
/ \
5 3
/
2
Step 2: Heapify root.
Final Heap:
5
/ \
4 3
/
2
Implementación :
C++
// C++ program for implement deletion in Heaps
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index of arr[] and n is the size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with last element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
deleteRoot(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java program for implement deletion in Heaps
public class deletionHeap {
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
static int deleteRoot(int arr[], int n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
// return new size of Heap
return n;
}
/* A utility function to print array of size N */
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = arr.length;
n = deleteRoot(arr, n);
printArray(arr, n);
}
}
Python3
# Python 3 program for implement deletion in Heaps # To heapify a subtree rooted with node i which is # an index of arr[] and n is the size of heap def heapify(arr, n, i): largest = i #Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 #If left child is larger than root if (l < n and arr[l] > arr[largest]): largest = l #If right child is larger than largest so far if (r < n and arr[r] > arr[largest]): largest = r # If largest is not root if (largest != i): arr[i],arr[largest]=arr[largest],arr[i] #Recursively heapify the affected sub-tree heapify(arr, n, largest) #Function to delete the root from Heap def deleteRoot(arr): global n # Get the last element lastElement = arr[n - 1] # Replace root with last element arr[0] = lastElement # Decrease size of heap by 1 n = n - 1 # heapify the root node heapify(arr, n, 0) # A utility function to print array of size n def printArray(arr, n): for i in range(n): print(arr[i],end=" ") print() # Driver Code if __name__ == '__main__': # Array representation of Max-Heap # 10 # / \ # 5 3 # / \ # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot(arr) printArray(arr, n) # This code is contributed by Rajat Kumar.
C#
// C# program for implement deletion in Heaps
using System;
public class deletionHeap
{
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
static void heapify(int []arr, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
static int deleteRoot(int []arr, int n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
// return new size of Heap
return n;
}
/* A utility function to print array of size N */
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
public static void Main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int []arr = { 10, 5, 3, 2, 4 };
int n = arr.Length;
n = deleteRoot(arr, n);
printArray(arr, n);
}
}
// This code is contributed by Ryuga
Javascript
<script>
// Javascript program for implement deletion in Heaps
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
function heapify(arr, n, i)
{
let largest = i; // Initialize largest as root
let l = 2 * i + 1; // left = 2*i + 1
let r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
let swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
function deleteRoot(arr, n)
{
// Get the last element
let lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
// return new size of Heap
return n;
}
/* A utility function to print array of size N */
function printArray(arr, n)
{
for (let i = 0; i < n; ++i)
document.write(arr[i] + " ");
document.write("</br>");
}
let arr = [ 10, 5, 3, 2, 4 ];
let n = arr.length;
n = deleteRoot(arr, n);
printArray(arr, n);
// This code is contributed by divyeshrabdiya07.
</script>
Producción:
5 4 3 2
Complejidad de tiempo : O (logn) donde n no es ningún elemento en el montón
Espacio Auxiliar: O(n)
Inserción en Montones
La operación de inserción también es similar a la del proceso de eliminación.
Dado un montón binario y un nuevo elemento que se agregará a este montón. La tarea es insertar el nuevo elemento en el Montón manteniendo las propiedades del Montón.
Proceso de inserción : los elementos se pueden insertar en el montón siguiendo un enfoque similar al discutido anteriormente para la eliminación. La idea es:
- Primero aumente el tamaño del almacenamiento dinámico en 1, para que pueda almacenar el nuevo elemento.
- Inserte el nuevo elemento al final del Heap.
- Este elemento recién insertado puede distorsionar las propiedades de Heap para sus padres. Entonces, para mantener las propiedades de Heap, apile este elemento recién insertado siguiendo un enfoque de abajo hacia arriba.
Ilustración :
Suppose the Heap is a Max-Heap as:
10
/ \
5 3
/ \
2 4
The new element to be inserted is 15.
Process:
Step 1: Insert the new element at the end.
10
/ \
5 3
/ \ /
2 4 15
Step 2: Heapify the new element following bottom-up
approach.
-> 15 is more than its parent 3, swap them.
10
/ \
5 15
/ \ /
2 4 3
-> 15 is again more than its parent 10, swap them.
15
/ \
5 10
/ \ /
2 4 3
Therefore, the final heap after insertion is:
15
/ \
5 10
/ \ /
2 4 3
Implementación :
C++
// C++ program to insert new element to Heap
#include <iostream>
using namespace std;
#define MAX 1000 // Max size of Heap
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
void heapify(int arr[], int n, int i)
{
// Find parent
int parent = (i - 1) / 2;
if (arr[parent] > 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);
// Recursively heapify the parent node
heapify(arr, n, parent);
}
}
}
// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;
// Insert the element at end of Heap
arr[n - 1] = Key;
// Heapify the new node following a
// Bottom-up approach
heapify(arr, n, n - 1);
}
// A utility function to print array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[MAX] = { 10, 5, 3, 2, 4 };
int n = 5;
int key = 15;
insertNode(arr, n, key);
printArray(arr, n);
// Final Heap will be:
// 15
// / \
// 5 10
// / \ /
// 2 4 3
return 0;
}
Java
// Java program for implementing insertion in Heaps
public class insertionHeap {
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
static void heapify(int[] arr, int n, int i)
{
// Find parent
int parent = (i - 1) / 2;
if (arr[parent] > 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
// swap arr[i] and arr[parent]
int temp = arr[i];
arr[i] = arr[parent];
arr[parent] = temp;
// Recursively heapify the parent node
heapify(arr, n, parent);
}
}
}
// Function to insert a new node to the heap.
static int insertNode(int[] arr, int n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;
// Insert the element at end of Heap
arr[n - 1] = Key;
// Heapify the new node following a
// Bottom-up approach
heapify(arr, n, n - 1);
// return new size of Heap
return n;
}
/* A utility function to print array of size n */
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
System.out.println(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
// maximum size of the array
int MAX = 1000;
int[] arr = new int[MAX];
// initializing some values
arr[0] = 10;
arr[1] = 5;
arr[2] = 3;
arr[3] = 2;
arr[4] = 4;
// Current size of the array
int n = 5;
// the element to be inserted
int Key = 15;
// The function inserts the new element to the heap and
// returns the new size of the array
n = insertNode(arr, n, Key);
printArray(arr, n);
// Final Heap will be:
// 15
// / \
// 5 10
// / \ /
// 2 4 3
}
}
// The code is contributed by Gautam goel
Python3
# program to insert new element to Heap # Function to heapify ith node in a Heap # of size n following a Bottom-up approach def heapify(arr, n, i): parent = int(((i-1)/2)) # For Max-Heap # If current node is greater than its parent # Swap both of them and call heapify again # for the parent if arr[parent] > 0: if arr[i] > arr[parent]: arr[i], arr[parent] = arr[parent], arr[i] # Recursively heapify the parent node heapify(arr, n, parent) # Function to insert a new node to the Heap def insertNode(arr, key): global n # Increase the size of Heap by 1 n += 1 # Insert the element at end of Heap arr.append(key) # Heapify the new node following a # Bottom-up approach heapify(arr, n, n-1) # A utility function to print array of size n def printArr(arr, n): for i in range(n): print(arr[i], end=" ") # Driver Code # Array representation of Max-Heap ''' 10 / \ 5 3 / \ 2 4 ''' arr = [10, 5, 3, 2, 4, 1, 7] n = 7 key = 15 insertNode(arr, key) printArr(arr, n) # Final Heap will be: ''' 15 / \ 5 10 / \ / 2 4 3 Code is written by Rajat Kumar.... '''
Producción:
15 5 10 2 4 3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA