欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

基于完全二叉树的堆排序（c++）

程序员文章站 2024-02-13 23:26:46
...

一，将数组转存为完全二叉树(未排序)

详情见之前的博文（戳这里）

二，什么是堆排序？有哪几种？

①堆排序是对二叉树的排序
②类别
（一）最大堆：父亲节点的值大于或等于所有孩子节点的值
（二）最小堆：父亲节点的值小于或等于所有孩子节点的值
基于完全二叉树的堆排序（c++）

三，最大堆算法设计

①最大堆就是确保每个父亲节点大于两个孩子节点，故采用递归的方式，确定是否每一个父亲节点的值是否大于两个孩子节点的值，如果该父亲节点的值小于孩子节点，进行值交换。
②每次进行过值交换，产生一个新堆，就要结束递归，再对新堆进行递归。故递归函数的返回值类型为bool，递归函数如下

bool sortHeap(NODE *root)
{
    if(root->left_children !=NULL && root->left_children->i>root->i) // 左孩子节点的值大于父亲节点的值，进行值交换，并结束递归
    {
        int temp = root->left_children->i;
        root->left_children->i = root-> i;
        root->i = temp;
        return false;
    }
    if(root->right_children !=NULL && root->right_children->i>root->i)// 左孩子节点的值大于父亲节点的值，进行值交换，并结束递归
    {
        int temp = root->right_children->i;
        root->right_children->i = root-> i;
        root->i = temp;
        return false;
    }
    if(root->left_children != NULL) // 对左孩子递归
       if( !sortHeap(root->left_children) )
           return false;
    if(root->right_children != NULL) // 对右孩子递归
       if( !sortHeap(root->right_children))
           return false;

    return true; // 以当前节点为根节点的堆符合最大堆，达到局部最优解
}

如果递归返回false证明产生了新堆还没有达到最大堆，故继续递归，直到返回true，代码如下：

void get_max_heap(NODE *root){
    while(true){
        if(sortHeap(root)) 
            break;  // 进行无数次递归，直到递归返回true，证明构成最大堆
    }
    cout<<"sort success"<<endl;
}

在main函数中调用，结果如图：
基于完全二叉树的堆排序（c++）
main函数

int main()
{
    cout<<"array length:";
    int l,temp;
    cin>>l; //输入数组长度
  int *x = new int[l];
  for(int i = 0 ; i<l ; i++){ //初始化数组
    cout<<"no."<<i+1<<":";
    cin>>temp;
        x[i]=temp;
  }
  NODE* root = new_node(NULL); //定义根节点
  map_tree(x,root,l); //根据数组构建完全二叉树
  print_tree(root); //打印未排序的二叉树
  get_max_heap(root); //生成最大堆
  cout<<endl; //换行
  print_tree(root); //打印最大堆
}

附（所有代码）

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;


typedef struct node{ //节点
    struct node* parent;
    int i;
    struct node* right_children;
    struct node* left_children;
}NODE;

typedef struct queue_t{ //队列
     NODE **node_list;
     int top;
     int bottom;
     int max_length;
}QUEUE;

NODE* new_node(NODE* parent); //初始化一个节点
void map_tree(int *x , NODE *root , int length); //根据数组生成完全二叉树
void print_tree(NODE* root); // 广度优先打印树
QUEUE* new_queue(int length); //初始化一个长度为length的队列
void push_queue(QUEUE *q,NODE *n);//压入队列
NODE* pop_queue(QUEUE *q);//冒出队列
void del_queue(QUEUE *q);//销毁队列
void print(NODE *parent);//深度优先打印树
bool sortHeap(NODE *root);// 最大堆的递归函数
void get_max_heap(NODE *root);//多次执行递归
int main()
{
    cout<<"array length:";
    int l,temp;
    cin>>l; //输入数组长度
  int *x = new int[l];
  for(int i = 0 ; i<l ; i++){ //初始化数组
    cout<<"no."<<i+1<<":";
    cin>>temp;
        x[i]=temp;
  }
  NODE* root = new_node(NULL); //定义根节点
  map_tree(x,root,l); //根据数组构建完全二叉树
  print_tree(root); //打印未排序的二叉树
  get_max_heap(root); //生成最大堆
  cout<<endl; //换行
  print_tree(root); //打印最大堆
}
NODE* new_node(NODE* parent){
    NODE* temp = new NODE();
    if(temp == NULL ){
        cout<<"NODE error"<<endl;
    }
    temp->parent = parent;
    temp->i=NULL;
    temp->right_children=NULL;
    temp->left_children=NULL;
    return temp;
}

void map_tree(int *x , NODE *root , int length)
{
     QUEUE *q = new_queue(100);
     push_queue(q,root);
     for(int i=0; i< length ; i++)
     {
         NODE* temp = pop_queue(q);
         temp->i = x[i];
         temp->left_children = new_node(temp);
         push_queue(q,temp->left_children);
         temp->right_children = new_node(temp);
         push_queue(q,temp->right_children);
     }
     while(true){
        NODE* temp = pop_queue(q);
        if(temp == NULL)
            break;
        else{
            NODE *parent = temp->parent;
            if(parent->left_children == temp)
              {
                  parent->left_children = NULL;
              }
             if(parent->right_children == temp)
              {
                  parent->right_children = NULL;
              }
            free(temp);

        }
     }
     del_queue(q);
}

void print_tree(NODE *root){
    int row=1;
    bool flag = true;
    QUEUE *q = new_queue(100);
    push_queue(q,root);
    while(flag){
       for(int i=0 ; i<row ; i++)
       {
           NODE *temp = pop_queue(q);
           if(temp == NULL)
           {
               flag = false;
               break;
           }
           cout<<temp->i<<" ";
           if(temp->left_children != NULL)
           push_queue(q,temp->left_children);
           if(temp->right_children != NULL)
           push_queue(q,temp->right_children);
       }
       row = 2*row;
       cout<<endl;
    }
    del_queue(q);
}

QUEUE* new_queue(int length){
    QUEUE *queue_tmp = new QUEUE();
    if(queue_tmp == NULL){
        cout<<"error"<<endl;
    }
    queue_tmp->node_list = new NODE*[length];
    if(queue_tmp->node_list == NULL){
        cout<<"error"<<endl;
    }
    queue_tmp->top = 0;
    queue_tmp->max_length=length;
    queue_tmp->bottom = 0;
    return queue_tmp;
}
void push_queue(QUEUE *q,NODE *n){
    if((q->top+1)%(q->max_length+1) == q->bottom)
        return;
    q->node_list[q->top] = n;
    q->top = (q->top+1)%(q->max_length+1);
}
NODE* pop_queue(QUEUE *q){
    if(q->bottom == q->top)
        return NULL;
    NODE *temp = q->node_list[q->bottom];
    q->bottom = (q->bottom+1)%(q->max_length+1);
    return temp;
}
void del_queue(QUEUE *q)
{
    free(q->node_list);
    free(q);
}
void print(NODE *parent)
{
    if(parent->left_children != NULL)
        print(parent->left_children);
    if(parent->right_children != NULL)
        print(parent->right_children);
    cout<<parent->i<<" ";
}
bool sortHeap(NODE *root)
{
    if(root->left_children !=NULL && root->left_children->i>root->i) // 左孩子节点的值大于父亲节点的值，进行值交换，并结束递归
    {
        int temp = root->left_children->i;
        root->left_children->i = root-> i;
        root->i = temp;
        return false;
    }
    if(root->right_children !=NULL && root->right_children->i>root->i)// 左孩子节点的值大于父亲节点的值，进行值交换，并结束递归
    {
        int temp = root->right_children->i;
        root->right_children->i = root-> i;
        root->i = temp;
        return false;
    }
    if(root->left_children != NULL) // 对左孩子递归
       if( !sortHeap(root->left_children) )
           return false;
    if(root->right_children != NULL) // 对右孩子递归
       if( !sortHeap(root->right_children))
           return false;

    return true; // 以当前节点为根节点的堆符合最大堆，达到局部最优解
}
void get_max_heap(NODE *root){
    while(true){
        if(sortHeap(root))
            break; // 进行无数次递归，直到递归返回true，证明构成最大堆
    }
    cout<<"sort success"<<endl;
}
相关标签： c++ 完全二叉树 堆排序 最大堆

上一篇： 剑指offer：Python 最小的k个数 多种方法实现 最大堆和最小堆

下一篇： Sprinig Boot优雅实现接口幂等性---1

推荐阅读