Рубрики

Лексикографический порядок с использованием Heap Sort

Дан массив arr [] строк. Задача состоит в том, чтобы отсортировать массив в лексикографическом порядке, используя сортировку кучи .

Примеры:

Input: arr[] = { “banana”, “apple”, “mango”, “pineapple”, “orange” }
Output: apple banana mango orange pineapple

Input: arr[] = { “CAB”, “ACB”, “ABC”, “CBA”, “BAC” }
Output: ABC, ACB, BAC, BCA, CAB, CBA

Подход: основная идея заключается в использовании сортировки кучи, и здесь минимальная куча используется для печати в лексикографическом порядке.

Ниже приведена реализация подхода:

C ++

// реализация C ++ для печати
// строка в лексикографическом порядке
#include <iostream>
#include <string>

using namespace std;

  
// Используется для индекса в куче

int x = -1;

  
// Предопределение массива кучи
string heap[1000];

  
// Определение формирования кучи

void heapForm(string k)

{

    x++;

  

    heap[x] = k;

  

    int child = x;

  

    string tmp;

  

    int index = x / 2;

  

    // итеративный heapiFy

    while (index >= 0) {

  

        // Просто поменять местами элемент

        // меньше чем уже

        // сохраненный элемент

        if (heap[index] > heap[child]) {

  

            // Обмен текущего индекса

            // со своим ребенком

            tmp = heap[index];

            heap[index] = heap[child];

            heap[child] = tmp;

            child = index;

  

            // движемся вверх в

            // куча

            index = index / 2;

        }

        else {

            break;

        }

    }

}

  
// Определение кучи

void heapSort()

{

    int left1, right1;

  

    while (x >= 0) {

        string k;

        k = heap[0];

  

        // Принимая вывод

        // минимальный элемент

        cout << k << " ";

  

        // Установить первый элемент

        // как последний

        heap[0] = heap[x];

  

        // Уменьшение

        // размер строки

        x = x - 1;

  

        string tmp;

  

        int index = 0;

  

        int length = x;

  

        // Инициализация левого

        // и правильный индекс

        left1 = 1;

  

        right1 = left1 + 1;

  

        while (left1 <= length) {

  

            // Процесс сортировки кучи

            // Если корневой элемент

            // минимум, чем оба

            // потом ребенка ломать

            if (heap[index] <= heap[left1]

                && heap[index] <= heap[right1]) {

                break;

            }

  

            // В противном случае проверяем это

            // ребенок который

            // меньше, поменяйте их местами

            // родительский элемент

            else {

  

                // Обмен

                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;

                }

            }

  

            // Изменение левого индекса

            // и правильный индекс

            left1 = 2 * left1;

            right1 = left1 + 1;

        }

    }

}

  
// Вспомогательная функция

void sort(string k[], int n)

{

  

    // Для кучи

    for (int i = 0; i < n; i++) {

        heapForm(k[i]);

    }

  

    // Вызываем функцию сортировки кучи

    heapSort();

}

  
// Код драйвера

int main()

{

    string arr[] = { "banana", "orange", "apple",

                   "pineapple", "berries", "lichi" };

  

    int n = sizeof(arr) / sizeof(arr[0]);

  

    sort(arr, n);

}

Джава

// Реализация Java для печати
// строка в лексикографическом порядке

class GFG

{

  
// Используется для индекса в куче

static int x = -1;

  
// Предопределение массива кучи

static String []heap = new String[1000];

  
// Определение формирования кучи

static void heapForm(String k)

{

    x++;

  

    heap[x] = k;

  

    int child = x;

  

    String tmp;

  

    int index = x / 2;

  

    // итеративный heapiFy

    while (index >= 0

    {

  

        // Просто поменять местами элемент

        // меньше чем уже

        // сохраненный элемент

        if (heap[index].compareTo(heap[child]) > 0

        {

  

            // Обмен текущего индекса

            // со своим ребенком

            tmp = heap[index];

            heap[index] = heap[child];

            heap[child] = tmp;

            child = index;

  

            // движемся вверх в

            // куча

            index = index / 2;

        }

        else 

        {

            break;

        }

    }

}

  
// Определение кучи

static void heapSort()

{

    int left1, right1;

  

    while (x >= 0)

    {

        String k;

        k = heap[0];

  

        // Принимая вывод

        // минимальный элемент

        System.out.print(k + " ");

  

        // Установить первый элемент

        // как последний

        heap[0] = heap[x];

  

        // Уменьшение

        // размер строки

        x = x - 1;

  

        String tmp;

  

        int index = 0;

  

        int length = x;

  

        // Инициализация левого

        // и правильный индекс

        left1 = 1;

  

        right1 = left1 + 1;

  

        while (left1 <= length) 

        {

  

            // Процесс сортировки кучи

            // Если корневой элемент

            // минимум, чем оба

            // потом ребенка ломать

            if (heap[index].compareTo(heap[left1]) <= 0 && 

                heap[index].compareTo(heap[right1]) <= 0)

            {

                break;

            }

  

            // В противном случае проверяем это

            // ребенок который

            // меньше, поменяйте их местами

            // родительский элемент

            else

            {

  

                // Обмен

                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;

                }

            }

  

            // Изменение левого индекса

            // и правильный индекс

            left1 = 2 * left1;

            right1 = left1 + 1;

        }

    }

}

  
// Вспомогательная функция

static void sort(String k[], int n)

{

  

    // Для кучи

    for (int i = 0; i < n; i++) 

    {

        heapForm(k[i]);

    }

  

    // Вызываем функцию сортировки кучи

    heapSort();

}

  
// Код драйвера

public static void main(String[] args)

{

    String arr[] = {"banana", "orange", "apple",

                    "pineapple", "berries", "lichi" };

  

    int n = arr.length;

  

    sort(arr, n);

}

  
// Этот код предоставлен Rajput-Ji

python3

# Реализация Python3 для печати
# строка в лексикографическом порядке

  
# Используется для индекса в куче

x = -1;

  
# Предопределение массива кучи

heap = [0] * 1000;

  
# Определение формирования кучи

def heapForm(k):

    global x;

    x += 1;

  

    heap[x] = k;

  

    child = x;

  

    index = x // 2;

  

    # Итеративный heapiFy

    while (index >= 0):

  

        # Просто поменять местами, если элемент

        # меньше чем уже

        # сохраненный элемент

        if (heap[index] > heap[child]):

  

            # Обмен текущего индекса

            # со своим ребенком

            tmp = heap[index];

            heap[index] = heap[child];

            heap[child] = tmp;

            child = index;

  

            # Двигаясь вверх в

            # куча

            index = index // 2;

  

        else:

            break;

  
# Определение кучи сортировки

def heapSort():

    global x;

    while (x >= 0):

        k = heap[0];

  

        # Принимая вывод

        # минимальный элемент

        print(k, end = " ");

  

        # Установить первый элемент

        # как последний

        heap[0] = heap[x];

  

        # Уменьшение

        # размер строки

        x = x - 1;

  

        tmp = -1;

  

        index = 0;

  

        length = x;

  

        # Инициализация левого

        # и правильный индекс

        left1 = 1;

  

        right1 = left1 + 1;

  

        while (left1 <= length):

  

            # Процесс сортировки кучи

            # Если корневой элемент

            # минимум, чем оба

            # ребенка потом сломать

            if (heap[index] <= heap[left1] and 

                heap[index] <= heap[right1]):

                break;

  

            # В противном случае проверка этого

            # ребенок, который является

            # поменьше, поменяйте их местами

            # родительский элемент

            else:

  

                # Обмен

                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;

  

            # Изменение левого индекса

            # и правильный индекс

            left1 = 2 * left1;

            right1 = left1 + 1;

  
# Вспомогательная функция

def sort(k, n):

      

    # Для кучи

    for i in range(n):

        heapForm(k[i]);

  

    # Вызов функции сортировки кучи

    heapSort();

  
Код водителя

if __name__ == '__main__':

    arr = ["banana", "orange", "apple",

           "pineapple", "berries", "lichi"];

  

    n = len(arr);

  

    sort(arr, n);

  
# Этот код предоставлен PrinciRaj1992

C #

// C # реализация для печати
// строка в лексикографическом порядке

using System;

      

class GFG

{

  
// Используется для индекса в куче

static int x = -1;

  
// Предопределение массива кучи

static String []heap = new String[1000];

  
// Определение формирования кучи

static void heapForm(String k)

{

    x++;

  

    heap[x] = k;

  

    int child = x;

  

    String tmp;

  

    int index = x / 2;

  

    // итеративный heapiFy

    while (index >= 0) 

    {

  

        // Просто поменять местами элемент

        // меньше чем уже

        // сохраненный элемент

        if (heap[index].CompareTo(heap[child]) > 0) 

        {

  

            // Обмен текущего индекса

            // со своим ребенком

            tmp = heap[index];

            heap[index] = heap[child];

            heap[child] = tmp;

            child = index;

  

            // движемся вверх в

            // куча

            index = index / 2;

        }

        else

        {

            break;

        }

    }

}

  
// Определение кучи

static void heapSort()

{

    int left1, right1;

  

    while (x >= 0)

    {

        String k;

        k = heap[0];

  

        // Принимая вывод

        // минимальный элемент

        Console.Write(k + " ");

  

        // Установить первый элемент

        // как последний

        heap[0] = heap[x];

  

        // Уменьшение

        // размер строки

        x = x - 1;

  

        String tmp;

  

        int index = 0;

  

        int length = x;

  

        // Инициализация левого

        // и правильный индекс

        left1 = 1;

  

        right1 = left1 + 1;

  

        while (left1 <= length) 

        {

  

            // Процесс сортировки кучи

            // Если корневой элемент

            // минимум, чем оба

            // потом ребенка ломать

            if (heap[index].CompareTo(heap[left1]) <= 0 && 

                heap[index].CompareTo(heap[right1]) <= 0)

            {

                break;

            }

  

            // В противном случае проверяем, что ребенок

            // какой из них меньше, поменяйте их местами

            // родительский элемент

            else

            {

  

                // Обмен

                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;

                }

            }

  

            // Изменение левого индекса

            // и правильный индекс

            left1 = 2 * left1;

            right1 = left1 + 1;

        }

    }

}

  
// Вспомогательная функция

static void sort(String []k, int n)

{

  

    // Для кучи

    for (int i = 0; i < n; i++) 

    {

        heapForm(k[i]);

    }

  

    // Вызываем функцию сортировки кучи

    heapSort();

}

  
// Код драйвера

public static void Main(String[] args)

{

    String []arr = {"banana", "orange", "apple",

                    "pineapple", "berries", "lichi" };

  

    int n = arr.Length;

  

    sort(arr, n);

}

  
// Этот код предоставлен Rajput-Ji

Выход:

apple banana berries lichi orange pineapple

Рекомендуемые посты:

Лексикографический порядок с использованием Heap Sort

0.00 (0%) 0 votes