如何为双向链表编写堆排序？ C++

Question

我需要为双向链表编写堆排序，但我无法实现该算法。你能帮帮我吗？

Answer 1

谢谢大家 - 有这样一个双向链表堆排序的工作代码 - 工作。也许以后会有人需要

void List::heap_sort(int n) {
Node* temp = Head;
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(temp, n, i);

   //По очереди извлекаем элементы из кучи
    for (int i = n - 1; i >= 0; i--)
    {
        swap(0, i, temp);

   
        heapify(temp, i, 0);
    }
}

void List::heapify(Node* temp, int n, int i) {
    // Инициализация большего элемента, как корня
    int largest = i; 
    int l = 2 * i + 1; 
    int r = 2 * i + 2; 
    Node* largesti = temp;
    for (int k = 0; k < largest; k++) {
        largesti = largesti->Next;
    }
    Node* li = temp;
    for (int k = 0; k < l; k++) {
        if (li == NULL)
            break;
        li = li->Next;
    }
    Node* ri = NULL;
    if (li != NULL) ri = li->Next;

    // Если правый потомок больше корня
    if (li != NULL)
    if (l < n && li->x > largesti->x) {
        largest = l;
        largesti = li;
    }
    // Если правый потомок до сих пор самый большой
        if (ri != NULL)
    if (r < n && ri->x > largesti->x)
        largest = r;

    // Если largest не является корнем
    if (largest != i)
    {
        swap(i, largest, temp);

        // Формируем дерево
        heapify(temp, n, largest);
    }
}

void List::swap(int i, int k, Node* swapList) {
    Node* temp1 = swapList, * temp2 = swapList;
    for (int j = 0; j < i; j++) {
        temp1 = temp1->Next;
    }
    for (int j = 0; j < k; j++) {
    temp2 = temp2->Next;
    }
    int number = temp1->x;
    temp1->x = temp2->x;

    temp2->x = number;

}

完整代码：

#include <iostream>
#include <fstream>
using namespace std;

struct Node                             
{
    int x;                             
    Node* Next, * Prev;                 
};

class List                             
{
    //Указатели на адреса начала списка и его конца
    Node* Head, * Tail;                 
public:
    //Инициализируем адреса как пустые
    List() :Head(NULL), Tail(NULL) {};    
    ~List();                           
    void show();                       
    void output_to_file(int c);
    void add(double x);                  
    void bubble_sort();
    void heap_sort(int n);
    void swap(int i, int k, Node* swapList);
    void heapify(Node* temp, int n, int i);
};

void List::add(double x)
{
    //Выделение памяти под новый элемент структуры
    Node* temp = new Node; 
    //Указываем, что изначально по следующему адресу пусто
    temp->Next = NULL;                   
    temp->x = x;                        

    if (Head != NULL)                   
    {
        temp->Prev = Tail;               
        Tail->Next = temp;               
        Tail = temp;                     
    }
    else
    {
        temp->Prev = NULL;               
        Head = Tail = temp;              
    }
}

void List::show()
{
    //Временно указываем на адрес первого элемента
    Node* temp = Head;  
    //Пока не встретим пустое значение
    while (temp != NULL)              
    {
        cout << temp->x << " ";        
        temp = temp->Next;             
    }
}

void List::output_to_file(int c)
{
    ofstream fout;
    fout.open("output.txt");
    if (fout.is_open()) {
        Node* temp = Head;                   
        fout << c << " ";
        while (temp != Tail)              
        {
            fout << temp->x << " ";        
            temp = temp->Next;           
        }
        fout << temp->x;
    }
    else
        cout << "Output file doesnt exist";
}

void List::bubble_sort() {
    //Первый элемент — это пусть будет голова
    Node* left = Head;                 
    //Второй элемент — это пусть будет следующий за головой элемент
    Node* right = Head->Next;          

    Node* temp = new Node;             

    while (left->Next) {                 
        while (right) {             
            if ((left->x) > (right->x)) {        
                temp->x = left->x;              
                left->x = right->x;            
                right->x = temp->x;            
            }
            right = right->Next;                    
        }
        left = left->Next;                              
        right = left->Next;                             
   }
}


void List::heap_sort(int n) {
    Node* temp = Head;
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(temp, n, i);

   //По очереди извлекаем элементы из кучи
    for (int i = n - 1; i >= 0; i--)
    {
        swap(0, i, temp);

   
        heapify(temp, i, 0);
    }
}

void List::heapify(Node* temp, int n, int i) {
    // Инициализация большего элемента, как корня
    int largest = i; 
    int l = 2 * i + 1; 
    int r = 2 * i + 2; 
    Node* largesti = temp;
    for (int k = 0; k < largest; k++) {
        largesti = largesti->Next;
    }
    Node* li = temp;
    for (int k = 0; k < l; k++) {
        if (li == NULL)
            break;
        li = li->Next;
    }
    Node* ri = NULL;
    if (li != NULL) ri = li->Next;

    // Если правый потомок больше корня
    if (li != NULL)
    if (l < n && li->x > largesti->x) {
        largest = l;
        largesti = li;
    }
    // Если правый потомок до сих пор самый большой
    if (ri != NULL)
    if (r < n && ri->x > largesti->x)
        largest = r;

    // Если largest не является корнем
    if (largest != i)
    {
        swap(i, largest, temp);

        // Формируем дерево
        heapify(temp, n, largest);
    }
}

void List::swap(int i, int k, Node* swapList) {
    Node* temp1 = swapList, * temp2 = swapList;
    for (int j = 0; j < i; j++) {
        temp1 = temp1->Next;
    }
    for (int j = 0; j < k; j++) {
        temp2 = temp2->Next;
    }
    int number = temp1->x;
    temp1->x = temp2->x;

    temp2->x = number;

}

List::~List()                          
{
    while (Head)                      
    {
        Tail = Head->Next;            
        delete Head;                   
        Head = Tail;                   
    }
}

void adder(List &lst,int &b) {
    ifstream fin("input.txt");
    double k;
    fin >> b;
    while (fin >> k) {
        lst.add(k);
    }
}

int main()
{
    ifstream fin;
    List lst; 
    int b;
    double k;
    int c = 0;
    fin.open("input.txt");
    if (fin.is_open()) {
//counting the numbers of elements in file
        while (fin >> k) {
            c++;
        }
        fin.close();

        fin.open("input.txt");
        if (fin.is_open()) {

            adder(lst, b);
            lst.show();

            if (b == 0)
                lst.heap_sort(c - 1);
            else
                lst.bubble_sort();

            cout << endl;
            lst.show();
            lst.output_to_file(c - 1);
        }
        else
            cout << "Input file doesnt exist";
    }
    else
        cout << "Input file doesnt exist";
    return 0;
}

如何为双向链表编写堆排序？ C++

How can I write a heapsort for a doubly linked list? c++

sorting

heap

list

heapsort