Ordenación lexicográfica usando Heap Sort

Dada una array arr[] de strings. La tarea es ordenar la array en orden lexicográfico usando Heap Sort .
Ejemplos: 
 

Entrada: arr[] = { “plátano”, “manzana”, “mango”, “piña”, “naranja” } 
Salida: manzana plátano mango naranja piña
Entrada: arr[] = { “CAB”, “ACB”, “ ABC”, “CBA”, “BAC” } 
Salida: ABC, ACB, BAC, BCA, CAB, CBA 
 

Enfoque: La idea básica es usar Heap sort y aquí el min-heap se usa para imprimir en el orden lexicográfico.
A continuación se muestra la implementación del enfoque: 
 

C++

// C++ implementation to print
// the string in Lexicographical order
#include <iostream>
#include <string>
using namespace std;
 
// Used for index in heap
int x = -1;
 
// Predefining the heap array
string heap[1000];
 
// Defining formation of the heap
void heapForm(string k)
{
    x++;
 
    heap[x] = k;
 
    int child = x;
 
    string tmp;
 
    int index = x / 2;
 
    // Iterative heapiFy
    while (index >= 0) {
 
        // Just swapping if the element
        // is smaller than already
        // stored element
        if (heap[index] > heap[child]) {
 
            // Swapping the current index
            // with its child
            tmp = heap[index];
            heap[index] = heap[child];
            heap[child] = tmp;
            child = index;
 
            // Moving upward in the
            // heap
            index = index / 2;
        }
        else {
            break;
        }
    }
}
 
// Defining heap sort
void heapSort()
{
    int left1, right1;
 
    while (x >= 0) {
        string k;
        k = heap[0];
 
        // Taking output of
        // the minimum element
        cout << k << " ";
 
        // Set first element
        // as a last one
        heap[0] = heap[x];
 
        // Decrement of the
        // size of the string
        x = x - 1;
 
        string tmp;
 
        int index = 0;
 
        int length = x;
 
        // Initializing the left
        // and right index
        left1 = 1;
 
        right1 = left1 + 1;
 
        while (left1 <= length) {
 
            // Process of heap sort
            // If root element is
            // minimum than its both
            // of the child then break
            if (heap[index] <= heap[left1]
                && heap[index] <= heap[right1]) {
                break;
            }
 
            // Otherwise checking that
            // the child which one is
            // smaller, swap them with
            // parent element
            else {
 
                // Swapping
                if (heap[left1] < heap[right1]) {
                    tmp = heap[index];
                    heap[index] = heap[left1];
                    heap[left1] = tmp;
                    index = left1;
                }
 
                else {
                    tmp = heap[index];
                    heap[index] = heap[right1];
                    heap[right1] = tmp;
                    index = right1;
                }
            }
 
            // Changing the left index
            // and right index
            left1 = 2 * left1;
            right1 = left1 + 1;
        }
    }
}
 
// Utility function
void sort(string k[], int n)
{
 
    // To heapiFy
    for (int i = 0; i < n; i++) {
        heapForm(k[i]);
    }
 
    // Calling heap sort function
    heapSort();
}
 
// Driver Code
int main()
{
    string arr[] = { "banana", "orange", "apple",
                   "pineapple", "berries", "litchi" };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    sort(arr, n);
}

Java

// Java implementation to print
// the string in Lexicographical order
class GFG
{
 
// Used for index in heap
static int x = -1;
 
// Predefining the heap array
static String []heap = new String[1000];
 
// Defining formation of the heap
static void heapForm(String k)
{
    x++;
 
    heap[x] = k;
 
    int child = x;
 
    String tmp;
 
    int index = x / 2;
 
    // Iterative heapiFy
    while (index >= 0)
    {
 
        // Just swapping if the element
        // is smaller than already
        // stored element
        if (heap[index].compareTo(heap[child]) > 0)
        {
 
            // Swapping the current index
            // with its child
            tmp = heap[index];
            heap[index] = heap[child];
            heap[child] = tmp;
            child = index;
 
            // Moving upward in the
            // heap
            index = index / 2;
        }
        else
        {
            break;
        }
    }
}
 
// Defining heap sort
static void heapSort()
{
    int left1, right1;
 
    while (x >= 0)
    {
        String k;
        k = heap[0];
 
        // Taking output of
        // the minimum element
        System.out.print(k + " ");
 
        // Set first element
        // as a last one
        heap[0] = heap[x];
 
        // Decrement of the
        // size of the string
        x = x - 1;
 
        String tmp;
 
        int index = 0;
 
        int length = x;
 
        // Initializing the left
        // and right index
        left1 = 1;
 
        right1 = left1 + 1;
 
        while (left1 <= length)
        {
 
            // Process of heap sort
            // If root element is
            // minimum than its both
            // of the child then break
            if (heap[index].compareTo(heap[left1]) <= 0 &&
                heap[index].compareTo(heap[right1]) <= 0)
            {
                break;
            }
 
            // Otherwise checking that
            // the child which one is
            // smaller, swap them with
            // parent element
            else
            {
 
                // Swapping
                if (heap[left1].compareTo(heap[right1])< 0)
                {
                    tmp = heap[index];
                    heap[index] = heap[left1];
                    heap[left1] = tmp;
                    index = left1;
                }
 
                else
                {
                    tmp = heap[index];
                    heap[index] = heap[right1];
                    heap[right1] = tmp;
                    index = right1;
                }
            }
 
            // Changing the left index
            // and right index
            left1 = 2 * left1;
            right1 = left1 + 1;
        }
    }
}
 
// Utility function
static void sort(String k[], int n)
{
 
    // To heapiFy
    for (int i = 0; i < n; i++)
    {
        heapForm(k[i]);
    }
 
    // Calling heap sort function
    heapSort();
}
 
// Driver Code
public static void main(String[] args)
{
    String arr[] = {"banana", "orange", "apple",
                    "pineapple", "berries", "lichi" };
 
    int n = arr.length;
 
    sort(arr, n);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation to print
# the string in Lexicographical order
 
# Used for index in heap
x = -1;
 
# Predefining the heap array
heap = [0] * 1000;
 
# Defining formation of the heap
def heapForm(k):
    global x;
    x += 1;
 
    heap[x] = k;
 
    child = x;
 
    index = x // 2;
 
    # Iterative heapiFy
    while (index >= 0):
 
        # Just swapping if the element
        # is smaller than already
        # stored element
        if (heap[index] > heap[child]):
 
            # Swapping the current index
            # with its child
            tmp = heap[index];
            heap[index] = heap[child];
            heap[child] = tmp;
            child = index;
 
            # Moving upward in the
            # heap
            index = index // 2;
 
        else:
            break;
 
# Defining heap sort
def heapSort():
    global x;
    while (x >= 0):
        k = heap[0];
 
        # Taking output of
        # the minimum element
        print(k, end = " ");
 
        # Set first element
        # as a last one
        heap[0] = heap[x];
 
        # Decrement of the
        # size of the string
        x = x - 1;
 
        tmp = -1;
 
        index = 0;
 
        length = x;
 
        # Initializing the left
        # and right index
        left1 = 1;
 
        right1 = left1 + 1;
 
        while (left1 <= length):
 
            # Process of heap sort
            # If root element is
            # minimum than its both
            # of the child then break
            if (heap[index] <= heap[left1] and
                heap[index] <= heap[right1]):
                break;
 
            # Otherwise checking that
            # the child which one is
            # smaller, swap them with
            # parent element
            else:
 
                # Swapping
                if (heap[left1] < heap[right1]):
                    tmp = heap[index];
                    heap[index] = heap[left1];
                    heap[left1] = tmp;
                    index = left1;
 
                else:
                    tmp = heap[index];
                    heap[index] = heap[right1];
                    heap[right1] = tmp;
                    index = right1;
 
            # Changing the left index
            # and right index
            left1 = 2 * left1;
            right1 = left1 + 1;
 
# Utility function
def sort(k, n):
     
    # To heapiFy
    for i in range(n):
        heapForm(k[i]);
 
    # Calling heap sort function
    heapSort();
 
# Driver Code
if __name__ == '__main__':
    arr = ["banana", "orange", "apple",
           "pineapple", "berries", "lichi"];
 
    n = len(arr);
 
    sort(arr, n);
 
# This code is contributed by PrinciRaj1992

C#

// C# implementation to print
// the string in Lexicographical order
using System;
     
class GFG
{
 
// Used for index in heap
static int x = -1;
 
// Predefining the heap array
static String []heap = new String[1000];
 
// Defining formation of the heap
static void heapForm(String k)
{
    x++;
 
    heap[x] = k;
 
    int child = x;
 
    String tmp;
 
    int index = x / 2;
 
    // Iterative heapiFy
    while (index >= 0)
    {
 
        // Just swapping if the element
        // is smaller than already
        // stored element
        if (heap[index].CompareTo(heap[child]) > 0)
        {
 
            // Swapping the current index
            // with its child
            tmp = heap[index];
            heap[index] = heap[child];
            heap[child] = tmp;
            child = index;
 
            // Moving upward in the
            // heap
            index = index / 2;
        }
        else
        {
            break;
        }
    }
}
 
// Defining heap sort
static void heapSort()
{
    int left1, right1;
 
    while (x >= 0)
    {
        String k;
        k = heap[0];
 
        // Taking output of
        // the minimum element
        Console.Write(k + " ");
 
        // Set first element
        // as a last one
        heap[0] = heap[x];
 
        // Decrement of the
        // size of the string
        x = x - 1;
 
        String tmp;
 
        int index = 0;
 
        int length = x;
 
        // Initializing the left
        // and right index
        left1 = 1;
 
        right1 = left1 + 1;
 
        while (left1 <= length)
        {
 
            // Process of heap sort
            // If root element is
            // minimum than its both
            // of the child then break
            if (heap[index].CompareTo(heap[left1]) <= 0 &&
                heap[index].CompareTo(heap[right1]) <= 0)
            {
                break;
            }
 
            // Otherwise checking that the child
            // which one is smaller, swap them with
            // parent element
            else
            {
 
                // Swapping
                if (heap[left1].CompareTo(heap[right1]) < 0)
                {
                    tmp = heap[index];
                    heap[index] = heap[left1];
                    heap[left1] = tmp;
                    index = left1;
                }
 
                else
                {
                    tmp = heap[index];
                    heap[index] = heap[right1];
                    heap[right1] = tmp;
                    index = right1;
                }
            }
 
            // Changing the left index
            // and right index
            left1 = 2 * left1;
            right1 = left1 + 1;
        }
    }
}
 
// Utility function
static void sort(String []k, int n)
{
 
    // To heapiFy
    for (int i = 0; i < n; i++)
    {
        heapForm(k[i]);
    }
 
    // Calling heap sort function
    heapSort();
}
 
// Driver Code
public static void Main(String[] args)
{
    String []arr = {"banana", "orange", "apple",
                    "pineapple", "berries", "lichi" };
 
    int n = arr.Length;
 
    sort(arr, n);
}
}
 
// This code is contributed by Rajput-Ji

Publicación traducida automáticamente

Artículo escrito por kunalcodr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *