设计实现基于树表的堆排序算法

Question

想用树结构来写一个堆排序，是真写不出来；感觉对堆排序的原理不理解；数组上的堆调整都还好写，但是基于二叉树去写堆的调整，我感觉头都大了

Search.h（设计实现基于树表的堆排序算法）

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

#pragma once

#define N 10
#define ERROR -1

typedef int elementType;

struct Node
{
    elementType data;
    Node* left;
    Node* right;
};

class Search
{
public:
    void initSqListData(elementType sqList[N]);
    int searchRandomSqList(elementType key);
    int halfSearchSortSqList(elementType key);

    void bubbleSort();
    void insertSort();
    void selectSort();
    void mergeSort(int start, int end);
    void heapSort();
    void quickSort(int low, int high);
    void shellSort();

    void printSqList();

    void initNodeData(elementType nodeData[N]);
    void printNodeData();
    void heapSortNodeData();

private:
    elementType sqList[N]{};
    elementType tempSqList[N]{};
    Node* root;

    void merge(int start, int mid, int end);
    void heapAdjust(int low, int high);
    int partition(int low, int high);

    Node* initNodeData(elementType nodeData[N], int index);
    void heapAdjust(Node* low, Node* high);
};

#include "Search.h"

void Search::initSqListData(elementType sqList[N])
{
    for (int i = 0; i < N; i++)
    {
        this->sqList[i] = sqList[i];
    }
}

int Search::searchRandomSqList(elementType key)
{
    for (int i = 0; i < N; i++)
    {
        if (sqList[i] == key)
        {
            return i;
        }
    }
    return ERROR;
}

bool cmp(const elementType key1, const elementType key2)
{
    return key1 < key2;
}

int Search::halfSearchSortSqList(elementType key)
{
    sort(sqList, sqList + N, cmp);
    printSqList();

    int low = 0;
    int high = N - 1;
    int mid = (low + high) / 2;
    while (low <= high)
    {
        if (sqList[mid] == key)
        {
            return mid;
        }
        else if (sqList[mid] < key)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
        mid = (low + high) / 2;
    }

    return ERROR;
}

void Search::bubbleSort()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < N - i; j++)
        {
            if (sqList[j] < sqList[j - 1])
            {
                elementType temp = sqList[j];
                sqList[j] = sqList[j - 1];
                sqList[j - 1] = temp;
            }
        }
    }
}

void Search::insertSort()
{
    for (int i = 1; i < N; i++)
    {
        elementType temp = sqList[i];
        int j = i;
        while (j > 0 && temp < sqList[j - 1])
        {
            sqList[j] = sqList[j - 1];
            j--;
        }
        if (j != i)
        {
            sqList[j] = temp;
        }
    }
}

void Search::selectSort()
{
    int minIndex;
    for (int i = 0; i < N; i++)
    {
        minIndex = i;
        for (int j = i + 1; j < N; j++)
        {
            if (sqList[minIndex] > sqList[j])
            {
                minIndex = j;
            }
        }
        if (minIndex != i)
        {
            elementType temp = sqList[minIndex];
            sqList[minIndex] = sqList[i];
            sqList[i] = temp;
        }
    }
}

void Search::merge(int start, int mid, int end)
{
    int k = 0;
    int i = start;
    int  j = mid + 1;
    while (i <= mid && j <= end)
    {
        if (sqList[i] <= sqList[j])
        {
            tempSqList[k++] = sqList[i++];
        }
        else
        {
            tempSqList[k++] = sqList[j++];
        }
    }

    while (i <= mid)
    {
        tempSqList[k++] = sqList[i++];
    }
    while (j <= end)
    {
        tempSqList[k++] = sqList[j++];
    }

    for (int i = 0, j = start; i < k; i++, j++)
    {
        sqList[j] = tempSqList[i];
    }
}

void Search::mergeSort(int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    merge(start, mid, end);
}

void Search::heapAdjust(int low, int high)
{
    elementType temp = sqList[low];
    for (int i = 2 * low; i < high; i *= 2)
    {
        if (i < high && sqList[i] < sqList[i + 1])
        {
            i++;
        }
        if (temp >= sqList[i])
        {
            break;
        }
        sqList[low] = sqList[i];
        low = i;
    }
    sqList[low] = temp;
}

void Search::heapSort()
{
    for (int i = N / 2; i >= 0; i--)
    {
        heapAdjust(i, N);
    }

    for (int i = N - 1; i > 0; i--)
    {
        elementType temp = sqList[0];
        sqList[0] = sqList[i];
        sqList[i] = temp;
        heapAdjust(0, i - 1);
    }
}

int Search::partition(int low, int high)
{
    elementType temp = sqList[low];
    elementType pivot = sqList[low];
    while (low < high)
    {
        while (low < high && sqList[high] >= pivot)
        {
            high--;
        }
        sqList[low] = sqList[high];
        while (low < high && sqList[low] <= pivot)
        {
            low++;
        }
        sqList[high] = sqList[low];
    }
    sqList[low] = temp;
    return low;
}

void Search::quickSort(int low, int high)
{
    if (low < high)
    {
        int pivot = partition(low, high);
        quickSort(low, pivot - 1);
        quickSort(pivot + 1, high);
    }
}

void Search::shellSort()
{
    for (int step = N / 2; step >= 1; step /= 2)
    {
        for (int i = step; i < N; i++)
        {
            elementType temp = sqList[i];
            int j = i;
            while (j >= step && temp < sqList[j - step])
            {
                sqList[j] = sqList[j - step];
                j -= step;
            }
            if (j != i)
            {
                sqList[j] = temp;
            }
        }
    }
}

void Search::printSqList()
{
    for (int i = 0; i < N; i++)
    {
        cout << sqList[i] << " ";
    }
    cout << endl << endl;
}

void Search::initNodeData(elementType nodeData[N])
{
    root = initNodeData(nodeData, 0);
}

Node* Search::initNodeData(elementType nodeData[N], int index)
{
    if (index >= N)
    {
        return NULL;
    }
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL)
    {
        cout << "内存不足，空间分配出错";
        return NULL;
    }
    node->data = nodeData[index];

    Node* left = initNodeData(nodeData, 2 * index + 1);
    Node* right = initNodeData(nodeData, 2 * index + 2);
    node->left = left;
    node->right = right;
    return node;
}

void Search::printNodeData()
{
    if (root == NULL)
    {
        return;
    }
    queue<Node*> myQueue;
    myQueue.push(root);
    while (!myQueue.empty())
    {
        Node* node = myQueue.front();
        myQueue.pop();
        cout << node->data << " ";
        if (node->left != NULL)
        {
            myQueue.push(node->left);
        }
        if (node->right != NULL)
        {
            myQueue.push(node->right);
        }
    }
}

void Search::heapAdjust(Node* low, Node* high)
{
    elementType temp = low->data;
    Node* cur = low->left;
    Node* curRight = low->right;
    while (cur != high)
    {


        cur = cur->left;
    }

    low->data = temp;
}

void Search::heapSortNodeData()
{



}

#include "Search.h"

int main()
{
    /*
    elementType sqList[N] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    Search search;
    search.initSqListData(sqList);
    search.printSqList();
    cout << search.searchRandomSqList(7) << endl;
    cout << search.searchRandomSqList(11) << endl;

    cout << search.halfSearchSortSqList(7) << endl;
    cout << search.halfSearchSortSqList(11) << endl;
    */

    /*
    elementType sqList[N] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    Search search;
    search.initSqListData(sqList);
    search.bubbleSort();
    search.printSqList();

    search.initSqListData(sqList);
    search.bubbleSort();
    search.printSqList();

    search.initSqListData(sqList);
    search.insertSort();
    search.printSqList();

    search.initSqListData(sqList);
    search.selectSort();
    search.printSqList();

    search.initSqListData(sqList);
    search.mergeSort(0, N - 1);
    search.printSqList();

    search.initSqListData(sqList);
    search.heapSort();
    search.printSqList();

    search.initSqListData(sqList);
    search.quickSort(0, N - 1);
    search.printSqList();

    search.initSqListData(sqList);
    search.shellSort();
    search.printSqList();
    */

    
    elementType sqList[N] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    Search search;
    search.initNodeData(sqList);
    search.printNodeData();
    
}

来用GPT给我一个参考的也行呐，网上找不到基于二叉树的C++实现的堆排序

Answer 1

基于new bing加以修改过后的回答：

// 包含头文件和使用命名空间
#include <iostream>
#include <queue>
using namespace std;

// 树节点结构体
struct Node {
int key;
Node *left, *right;
};

// 新建节点
Node* newNode(int key) {
Node* node = new Node;
node->key = key;
node->left = node->right = nullptr;
return node;
}

// 中序遍历
void inorder(Node* root) {
if (root == nullptr)
return;

inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}

// 将数组构建为完全二叉树
Node* buildTree(int arr[], int n) {
// 新建根结点
Node* root = newNode(arr[0]);
// 创建一个队列并将根结点压入队列中
queue<Node*> q;
q.push(root);

int i = 1;
// 当队列不为空且数组还未遍历完成时，继续构建二叉树
while (!q.empty() && i < n) {
    // 取出队首元素
    Node* temp = q.front();
    q.pop();

    // 构建左孩子结点
    temp->left = newNode(arr[i++]);
    // 将左孩子结点压入队列中
    q.push(temp->left);

    if (i < n) {
        // 构建右孩子结点
        temp->right = newNode(arr[i++]);
        // 将右孩子结点压入队列中
        q.push(temp->right);
    }
}

return root;
}

// 调整堆
void heapify(Node* root) {
if (root == nullptr)
return;

Node *largest = root, *left = root->left, *right = root->right;

// 找到三个结点中键值最大的结点
if (left != nullptr && left->key > largest->key)
    largest = left;

if (right != nullptr && right->key > largest->key)
    largest = right;

// 如果最大的结点不是根结点，则交换键值并继续调整堆
if (largest != root) {
    swap(largest->key, root->key);
    heapify(largest);
}
}

// 构建大根堆
void buildHeap(Node* root) {
if (root == nullptr)
return;

// 后序遍历左右子树，先构建子树为大根堆，再将根结点加入堆中
buildHeap(root->left);
buildHeap(root->right);
heapify(root);
}

// 堆排序
void heapSort(Node* root) {
// 构建大根堆
buildHeap(root);
// 每次将堆顶元素输出，并将最后一个元素作为根结点（从而实现了排序），继续调整堆
while (root->key != INT_MIN) {
cout << root->key << " ";
root->key = INT_MIN;
heapify(root);
}
}

// 测试代码
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);

// 构建完全二叉树
Node* root = buildTree(arr, n);

// 中序遍历二叉树
cout << "Inorder traversal before sorting: \n";
inorder(root);

// 堆排序并输出结果
cout << "\nSorted array is \n";
heapSort(root);

return 0;
}