HeapSort es una técnica de clasificación basada en la comparación en la que primero construimos Max Heap y luego intercambiamos el elemento raíz con el último elemento (tamaño veces) y mantenemos la propiedad del montón cada vez para finalmente ordenarlo.
Ejemplos:
Input : 10 20 15 17 9 21 Output : 9 10 15 17 20 21 Input: 12 11 13 5 6 7 15 5 19 Output: 5 5 6 7 11 12 13 15 19
En el primer ejemplo, primero tenemos que construir Max Heap.
Entonces, comenzaremos desde 20 como niño y buscaremos a su padre. Aquí 10 es más pequeño, así que intercambiaremos estos dos.
Ahora, 20 10 15 17 9 21
Ahora, el hijo 17 es mayor que su padre 10. Entonces, ambos se intercambiarán y el orden será 20 17 15 10 9 21
Ahora, el hijo 21 es mayor que el padre 15. Entonces, ambos se intercambiarán.
20 17 21 10 9 15
Ahora, nuevamente 21 es más grande que el padre 20. Entonces, 21 17 20 10 9 15
Este es Max Heap.
Ahora, tenemos que aplicar la ordenación. Aquí, tenemos que intercambiar el primer elemento con el último y tenemos que mantener la propiedad Max Heap. Entonces, después del primer intercambio: 15 17 20 10 9 21 Claramente viola la propiedad Max Heap.
Entonces, tenemos que mantenerlo. Entonces, el orden será
20 17 15 10 9 21
17 10 15 9 20 21
15 10 9 17 20 21
10 9 15 17 20 21
9 10 15 17 20 21
Aquí, la parte subrayada es parte ordenada.
C++
// C++ program for implementation
// of Iterative Heap Sort
#include <bits/stdc++.h>
using namespace std;
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
void buildMaxHeap(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
// if child is bigger than parent
if (arr[i] > arr[(i - 1) / 2])
{
int j = i;
// swap child and parent until
// parent is smaller
while (arr[j] > arr[(j - 1) / 2])
{
swap(arr[j], arr[(j - 1) / 2]);
j = (j - 1) / 2;
}
}
}
}
void heapSort(int arr[], int n)
{
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--)
{
// swap value of first indexed
// with last indexed
swap(arr[0], arr[i]);
// maintaining heap property
// after each swapping
int j = 0, index;
do
{
index = (2 * j + 1);
// if left child is smaller than
// right child point index variable
// to right child
if (arr[index] < arr[index + 1] &&
index < (i - 1))
index++;
// if parent is smaller than child
// then swapping parent with child
// having higher value
if (arr[j] < arr[index] && index < i)
swap(arr[j], arr[index]);
j = index;
} while (index < i);
}
}
// Driver Code to test above
int main()
{
int arr[] = {10, 20, 15, 17, 9, 21};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Given array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n\n");
heapSort(arr, n);
// print array after sorting
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C
// C program for implementation
// of Iterative Heap Sort
#include <stdio.h>
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
void buildMaxHeap(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
// if child is bigger than parent
if (arr[i] > arr[(i - 1) / 2])
{
int j = i;
// swap child and parent until
// parent is smaller
while (arr[j] > arr[(j - 1) / 2])
{
int temp=arr[j];
arr[j]=arr[(j-1)/2];
arr[(j-1)/2]=temp;
j = (j - 1) / 2;
}
}
}
}
void heapSort(int arr[], int n)
{
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--)
{
// swap value of first indexed
// with last indexed
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
// maintaining heap property
// after each swapping
int j = 0, index;
do
{
index = (2 * j + 1);
// if left child is smaller than
// right child point index variable
// to right child
if (arr[index] < arr[index + 1] &&
index < (i - 1))
index++;
// if parent is smaller than child
// then swapping parent with child
// having higher value
if (arr[j] < arr[index] && index < i)
{
int tem1=arr[j];
arr[j]=arr[index];
arr[index]=tem1;
}
j = index;
} while (index < i);
}
}
// Driver Code to test above
int main()
{
int arr[] = {10, 20, 15, 17, 9, 21};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Given array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n\n");
heapSort(arr, n);
// print array after sorting
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Java
// Java implementation of Iterative Heap Sort
public class HeapSort {
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
static void buildMaxHeap(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
// if child is bigger than parent
if (arr[i] > arr[(i - 1) / 2])
{
int j = i;
// swap child and parent until
// parent is smaller
while (arr[j] > arr[(j - 1) / 2])
{
swap(arr, j, (j - 1) / 2);
j = (j - 1) / 2;
}
}
}
}
static void heapSort(int arr[], int n)
{
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--)
{
// swap value of first indexed
// with last indexed
swap(arr, 0, i);
// maintaining heap property
// after each swapping
int j = 0, index;
do
{
index = (2 * j + 1);
// if left child is smaller than
// right child point index variable
// to right child
if (index < (i - 1) && arr[index] < arr[index + 1])
index++;
// if parent is smaller than child
// then swapping parent with child
// having higher value
if (index < i && arr[j] < arr[index])
swap(arr, j, index);
j = index;
} while (index < i);
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i]=a[j];
a[j] = temp;
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {10, 20, 15, 17, 9, 21};
int n = arr.length;
System.out.print("Given array: ");
printArray(arr);
heapSort(arr, n);
System.out.print("Sorted array: ");
printArray(arr);
}
}
Python3
# Python3 program for implementation
# of Iterative Heap Sort
# function build Max Heap where value
# of each child is always smaller
# than value of their parent
def buildMaxHeap(arr, n):
for i in range(n):
# if child is bigger than parent
if arr[i] > arr[int((i - 1) / 2)]:
j = i
# swap child and parent until
# parent is smaller
while arr[j] > arr[int((j - 1) / 2)]:
(arr[j],
arr[int((j - 1) / 2)]) = (arr[int((j - 1) / 2)],
arr[j])
j = int((j - 1) / 2)
def heapSort(arr, n):
buildMaxHeap(arr, n)
for i in range(n - 1, 0, -1):
# swap value of first indexed
# with last indexed
arr[0], arr[i] = arr[i], arr[0]
# maintaining heap property
# after each swapping
j, index = 0, 0
while True:
index = 2 * j + 1
# if left child is smaller than
# right child point index variable
# to right child
if (index < (i - 1) and
arr[index] < arr[index + 1]):
index += 1
# if parent is smaller than child
# then swapping parent with child
# having higher value
if index < i and arr[j] < arr[index]:
arr[j], arr[index] = arr[index], arr[j]
j = index
if index >= i:
break
# Driver Code
if __name__ == '__main__':
arr = [10, 20, 15, 17, 9, 21]
n = len(arr)
print("Given array: ")
for i in range(n):
print(arr[i], end = " ")
print()
heapSort(arr, n)
# print array after sorting
print("Sorted array: ")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by PranchalK
C#
// C# implementation of Iterative Heap Sort
using System;
class HeapSort
{
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
static void buildMaxHeap(int []arr, int n)
{
for (int i = 1; i < n; i++)
{
// if child is bigger than parent
if (arr[i] > arr[(i - 1) / 2])
{
int j = i;
// swap child and parent until
// parent is smaller
while (arr[j] > arr[(j - 1) / 2])
{
swap(arr, j, (j - 1) / 2);
j = (j - 1) / 2;
}
}
}
}
static void heapSort(int []arr, int n)
{
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--)
{
// swap value of first indexed
// with last indexed
swap(arr, 0, i);
// maintaining heap property
// after each swapping
int j = 0, index;
do
{
index = (2 * j + 1);
// if left child is smaller than
// right child point index variable
// to right child
if (index < (i - 1) && arr[index] <
arr[index + 1])
index++;
// if parent is smaller than child
// then swapping parent with child
// having higher value
if (index < i && arr[j] < arr[index])
swap(arr, j, index);
j = index;
} while (index < i);
}
}
public static void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/* A utility function to print array of size n */
static void printArray(int []arr)
{
int n = arr.Length;
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
public static void Main(String []args)
{
int []arr = {10, 20, 15, 17, 9, 21};
int n = arr.Length;
Console.Write("Given array: ");
printArray(arr);
heapSort(arr, n);
Console.Write("Sorted array: ");
printArray(arr);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript program for implementation
// of Iterative Heap Sort
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
function buildMaxHeap(arr, n) {
for(let i=1;i<n;i++)
{
// if child is bigger than parent
if (arr[i] > arr[(i - 1) / 2])
{
let j = i;
// swap child and parent until
// parent is smaller
while (arr[j] > arr[(j - 1) / 2])
{
swap(arr,j,(j-1)/2);
j = (j - 1) / 2;
}
}
}
}
function heapSort(arr, n) {
buildMaxHeap(arr,n);
for (let i = n - 1; i > 0; i--)
{
// swap value of first indexed
// with last indexed
swap(arr,0,i);
// maintaining heap property
// after each swapping
let j = 0, index;
do
{
index = (2 * j + 1);
// if left child is smaller than
// right child point index variable
// to right child
if (arr[index] < arr[index + 1] && index < (i - 1))
index++;
// if parent is smaller than child
// then swapping parent with child
// having higher value
if (arr[j] < arr[index] && index < i)
swap(arr, j, index);
j = index;
} while (index < i);
}
}
// Driver Code to test above
let arr = [10, 20, 15, 17, 9, 21];
let n = arr.length;
document.write("Given array : ");
for (let i = 0; i < n; ++i)
document.write(arr[i]+" ");
document.write("<br>");
heapSort(arr,n);
// print array after sorting
document.write("Sorted array : ");
for (let i = 0; i < n; ++i)
document.write(arr[i]+" ");
// This code is contributed by aditya942003patil
</script>
Producción :
Given array: 10 20 15 17 9 21 Sorted array: 9 10 15 17 20 21
Aquí, tanto la función buildMaxHeap como heapSort se ejecutan en tiempo O (nlogn). Entonces, la complejidad del tiempo general es O (nlogn)
Publicación traducida automáticamente
Artículo escrito por kaditya139 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA