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

数据结构复习6, 堆,堆排序

程序员文章站 2022-06-04 09:13:04
...

堆是什么

简单的来说, 堆就是使用数组而生成的二叉树. 不同于搜索二叉树的是, 搜索二叉树左孩子永远要比右孩子要小。而堆则分为最大堆以及最小堆. 最大堆的意思就是说从root开始, 它的每个子树都要比root小, 最小堆则与最大堆相反.

数据结构复习6, 堆,堆排序

堆的实现,以及排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define parent(x) (x-1)/2
#define left(x)   (2*x)+1
#define right(x)  (2*x)+2

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void Create_Max_Heap(int* data, int size)
{
    for(int i = 1; i < size;i++)
    {
        int child = i;
        while(child > 0)
        {
            int root = parent(child);
            if(data[root] < data[child])
            {
                swap(&(data[root]), &(data[child]));
            }
            child = root;
        }
    }
}

void Create_Min_Heap(int* data, int size)
{
    for(int i = 1; i< size;i++)
    {
        int child = i;
        while(child > 0)
        {
            int root = parent(child);
            if(data[root] > data[child])
            {
                swap((&data[root]), (&data[child]));
            }
            child = root;
        }
    }
}

//option = 1,从小到大
//option = 0,从大到小

void Heap_sort(int* data,int size,int option)
{
    for(int i = size -1; i>=0; i--)
    {
        swap(&data[0], &data[i]);
        
        switch (option) {
            case 1:
                Create_Max_Heap(data, i);
                break;
            case 0:
                Create_Min_Heap(data, i);
                break;
        }
        
    }
}

void print_heap(int* data, int size)
{
    for(int i = 0; i< size;i++)
    {
        printf("%d ",data[i]);
    }
    printf("\n");
}

int main()
{
    int data[10];
    srand((unsigned)time(NULL));
    
    for(int i = 0; i< 10; i++)
    {
        int temp = rand()%10+1;
        printf("%d ",temp);
        data[i] = temp;
    }
    printf("\n");
    
    //从小到大
    Create_Max_Heap(data, 10);
    Heap_sort(data, 10,1);
    print_heap(data, 10);
    
    //从大到小
    Create_Min_Heap(data, 10);
    Heap_sort(data, 10, 0);
    print_heap(data, 10);
}