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

数据结构堆的实现以及堆的面试题

程序员文章站 2024-02-11 19:40:16
...

堆的特点

堆有大堆和小堆之分

小堆:
①任意结点的关键码均小于等于他的左右孩子的关键码
②位于堆顶的结点的关键码最小
③从根结点到每个结点的路径上数组元素组成的序列都是递增的

大堆:
①任意结点的关键码均大于等于他的左右孩子的关键码
②位于堆顶的结点的关键码最大
③从根结点到每个结点的路径上数组元素组成的序列都是递减的

数据结构堆的实现以及堆的面试题

堆存储在下标为0的数组中,因此在堆中给定下标为i的结点时有:
①如果i=0,结点i是根节点,没有双亲节点;否则结点i的双亲结点为
结点(i-1)/2
②如果2 * i + 1 <= n - 1(n为堆中结点个数),则结点i的左孩子为结
点2 * i + 1,否则结点i无左孩子
③如果2 * i + 2 <= n - 1(同上),则结点i的右孩子为结点2 * i + 2,
否则结点i无右孩子

堆的实现

heap.h

#pragma once

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

typedef int HPDataType;
typedef int (*PCompare)(HPDataType left, HPDataType right);//函数指针,用小堆就选Less,用大堆就选Greater
typedef struct Heap
{
    HPDataType *_hp;
    int _size;//堆中的元素个数
    int _capacity;//堆的容量
    PCompare _com;
}Heap;

// 小于比较 
int Less(HPDataType left, HPDataType right);
// 大于比较 
int Greater(HPDataType left, HPDataType right);
// 初始化堆 
void InitHeap(Heap* hp);
// 创建堆 
void CreateHeap(Heap* hp, int* array, int size, PCompare com);
//检查扩容
void _CheckCapacity(Heap* hp);
// 在堆中插入元素data 
void InsertHeap(Heap* hp, HPDataType data);
// 删除堆顶的元素 
void RemoveHeap(Heap* hp);
// 获取堆中有效元素个数 
int SizeHeap(Heap* hp);
// 检测堆是否为空 
int EmptyHeap(Heap* hp);
// 获取堆顶元素 
HPDataType TopHeap(Heap* hp);
// 销毁堆 
void DestroyHeap(Heap* hp);
// 向下调整 
void AdjustDown(Heap* hp, int parent);
// 向上调整 
void AdjustUp(Heap* hp, int child);
heap.c


#include "heap.h"


int Less(HPDataType left, HPDataType right)
{
    return left < right;
}

int Greater(HPDataType left, HPDataType right)
{
    return left > right;
}

void InitHeap(Heap* hp)
{
    assert(hp);
    hp->_hp = (HPDataType*)malloc(3 * sizeof(HPDataType));//初始化开辟多少都行
    hp->_capacity = 3;
    hp->_size = 0;
}

void Swap(HPDataType *left, HPDataType*right)
{
    HPDataType tmp = 0;
    tmp = *left;
    *left = *right;
    *right = tmp;
}

void AdjustUp(Heap* hp, int child)
{
    assert(hp);
    int parent = (child - 1) / 2;//找出父母结点下标
    while (child)//只要child还为非零,就继续循环
    {
        if (hp->_com(hp->_hp[child], hp->_hp[parent]))//是否需要父母结点
                                                      //与孩子结点交换关键码
        {
            Swap(&hp->_hp[child], &hp->_hp[parent]);
            child = parent;//此时孩子结点上移到父母结点
            parent = (child - 1) / 2;//计算新的父母结点
        }
        else
            return;
    }
}

void AdjustDown(Heap* hp, int parent)
{
    assert(hp);
    if (NULL == hp)
        return;
    int child = parent * 2 + 1;//计算左孩子结点下标
    while (child < hp->_size)//只要孩子结点下标不越界
    {
        if (child + 1 < hp->_size&&hp->_com(hp->_hp[child+1],hp->_hp[child]))
        //是否需要左右孩子交换关键码,我是以左孩子是否与父母交换关键码为前提
        {
            Swap(&hp->_hp[child], &hp->_hp[child + 1]);
        }
        if (hp->_com(hp->_hp[child], hp->_hp[parent]))//是否左孩子与父母交换关键码
        {
            Swap(&hp->_hp[child], &hp->_hp[parent]);
            parent = child;//父母结点移到孩子结点,当做下一个父母结点
            child = parent * 2 + 1;
        }
        else
            return;
    }
}

void CreateHeap(Heap* hp, int* array, int size, PCompare com)
{
    assert(hp);
    int root = (size - 2) / 2;//找到最后一个非叶子结点的结点
    int i = 0;
    hp->_hp = (HPDataType*)malloc(size * sizeof(HPDataType));
    if (hp == NULL)
        return;
    for (i = 0; i < size; i++)
    {
        hp->_hp[i] = array[i];
    }
    hp->_capacity = size;
    hp->_size = size;
    hp->_com = com;
    while (root>=0)//从当前结点一直向下调整到下标为零的结点
    {
        AdjustDown(hp,root);
        root--;
    }
}

void _CheckCapacity(Heap* hp)
{
    assert(hp);
    int i = 0;
    HPDataType *new = NULL;
    int newcapacity = hp->_capacity * 2;
    new = (HPDataType*)malloc(newcapacity * sizeof(HPDataType));
    if (new == NULL)
        return;
    for (i = 0; i < hp->_size; i++)
    {
        new[i] = hp->_hp[i];
    }
    free(hp->_hp);
    hp->_hp = new;
    hp->_capacity = newcapacity;
}

void InsertHeap(Heap* hp, HPDataType data)
{
    assert(hp);
    if (hp->_capacity == hp->_size)
        _CheckCapacity(hp);
    hp->_hp[hp->_size] = data;//一定要先插入后size++
    AdjustUp(hp, hp->_size);
    hp->_size++;
}

void RemoveHeap(Heap* hp)
{
    assert(hp);
    if (NULL == hp)
        return;
    hp->_hp[0] = hp->_hp[hp->_size - 1];
    hp->_size--;//一定要先size--,后向下调整,否则他会把删除的结点也调整了
    AdjustDown(hp, 0);
}

int SizeHeap(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

int EmptyHeap(Heap* hp)
{
    assert(hp);
    return 0 == hp->_size;
}

HPDataType TopHeap(Heap* hp)
{
    assert(hp);
    return hp->_hp[0];
}

void DestroyHeap(Heap* hp)
{
    assert(hp);
    if (hp)
    {
        free(hp);
        hp->_capacity = 0;
        hp->_size = 0;
    }
}

优先级队列

heap.h


typedef struct PriorityQueue
{
    Heap hp;
}PriorityQueue;

//初始化
void InitPriorityQueue(PriorityQueue* q);

//入队列
void PushPriorityQueue(PriorityQueue* q, HPDataType data);

//出队列
void PopPriorityQueue(PriorityQueue* q);

//取队头元素
void TopPriorityQueue(PriorityQueue* q);

//队列长度
int SizePriorityQueue(PriorityQueue* q);

//判空
int EmptyPriorityQueue(PriorityQueue* q);
heap.c


void InitPriorityQueue(PriorityQueue* q)
{
    InitHeap(&q->hp);
}

void PushPriorityQueue(PriorityQueue* q, HPDataType data)
{
    InsertHeap(&q->hp, data);
}

void PopPriorityQueue(PriorityQueue* q)
{
    RemoveHeap(&q->hp);
}

void TopPriorityQueue(PriorityQueue* q)
{
    return TopHeap(&q->hp);
}

int SizePriorityQueue(PriorityQueue* q)
{
    return SizeHeap(&q->hp);
}

int EmptyPriorityQueue(PriorityQueue* q)
{
    return EmptyHeap(&q->hp);
}

堆排序(降序,用小堆)

堆排序的原理
①将堆顶元素和堆中最后一个元素交换
②此时数组最后一个元素已经排好序了,因此将堆中元素减少一个
③此时堆结构可能被破坏,再向下调整使其满足堆的性质
④将以上三个步骤循环起来,直到排序完数组中的所有元素

void _AdjustDown(int *array, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size&&array[child + 1] < array[child])
        {
            Swap(&array[child + 1], &array[child]);
        }
        if (array[parent] > array[child])
        {
            Swap(&array[parent], &array[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            return;
    }
}
void MakeHeap(int *array, int size)
{
    int root = (size - 2) / 2;
    while (root >= 0)
    {
        _AdjustDown(array,size, root);
        root--;
    }
}

void HeapSort(int *array, int size)
{
    MakeHeap(array, size);//把传过来的数组创建成堆
    while (size)//调整完所有元素
    {
        Swap(&array[0], &array[size - 1]);//交换堆顶元素和堆中最后一个元素
        size--;//减少堆中元素一个
        _AdjustDown(array, size, 0);//向下调整
    }
}

测试

test.c


#include "heap.h"
int main()
{
    //Heap hp;//被注释了的是测试堆的实现的代码,没被注释的是测试堆排序的代码,优先级队列大家就自己测试吧
    int i = 0;
    int array[] = { 53,17,78,9,45,65,87,23,31 };
    //InitHeap(&hp);
    //CreateHeap(&hp, array, sizeof(array)/sizeof(array[0]), Less);
    //for (i = 0; i < hp._size; i++)
    //{
    //  printf("%d ", hp._hp[i]);
    //}
    //printf("\n");
    //printf("%d ", TopHeap(&hp));
    //printf("%d ", SizeHeap(&hp));
    //printf("\n");
    int size = sizeof(array) / sizeof(array[0]);
    HeapSort(array,size);
    for (i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    //InsertHeap(&hp,11);
    //for (i = 0; i < hp._size; i++)
    //{
    //  printf("%d ", hp._hp[i]);
    //}
    //printf("\n");
    //printf("%d ", TopHeap(&hp));
    //printf("%d ", SizeHeap(&hp));
    //printf("\n");
    //RemoveHeap(&hp);
    //for (i = 0; i < hp._size; i++)
    //{
    //  printf("%d ", hp._hp[i]);
    //}
    //printf("\n");
    //printf("%d ", TopHeap(&hp));
    //printf("%d ", SizeHeap(&hp));
    system("pause");
    return 0;
}
相关标签: 数据结构之堆