前言
此篇文章是使用完全二叉树实现小堆然后用小堆进行堆排序,堆排序的时间复杂度为logN空间复杂度为O(N);后续还会优化吧空间复杂度改一下
正文
先讲一下二叉树的储存结构吧
二叉树的储存结构
顺序结构
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们在后面会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
及顺序表按照从左到右从上到下的顺序依次储存.
顺序表存储的结构元素的双亲和孩子都是可以通过公式找到的
father = (child-1)/2; //一定是先-1再除二
child = father*2+1; //但是这个我们只能得到左孩子要想得到右孩子必须++
如果是非完全二叉树的格式就按照完全二叉树的将无元素的地区空出
链式结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。
链式结构就是按照普通的链表和指针进行连接.
typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }; // 三叉链 struct BinaryTreeNode { struct BinTreeNode* _pParent; // 指向当前节点的双亲 struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 };
堆的概念
我先讲一下自己的理解:
堆分为小堆和大堆,我讲一下小堆大家一定也就可以理解大堆了🤪.
讲道理还是图文来讲比较合适
先文字描述: 小堆就是根节点为所有数据中最小的,其他子结构的根也为最小的值.
图:
堆是一棵完全二叉树(一定是完全二叉树)
正式理解
二叉树的顺序结构的实现&堆的实现
堆的实现其实就是用二叉树的顺序结构实现的所以我干脆放在一起讲🤪.
我的思路还是先看整体代码再讲解代码实现难点.
来看一眼我们的代码们吧
Heap.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HPDataType; //通过顺序表实现树的堆 这个为小堆 typedef struct Heap { HPDataType* data; size_t size; size_t capacity; }Heap; //创建堆 void HeapCreat(Heap* obj); //摧毁堆 void HeapDestory(Heap* obj); //插入数据 void HeapPush(Heap*obj,HPDataType x); //数据打印 void HeapPrint(Heap* obj); //删除数据 void HeapPop(Heap* obj); //堆顶数据 HPDataType HeapTop(Heap* obj); //堆的个数 size_t HeapSize(Heap* obj); //堆的判空 bool HeapEmpty(Heap* obj);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" void HeapCreat(Heap* obj) { assert(obj); obj->data = (HPDataType*)malloc(sizeof(HPDataType)*4); assert(obj->data); obj->size = 0; obj->capacity = 4; } void HeapDestory(Heap* obj) { assert(obj); free(obj->data); obj->size = obj->capacity = 0; } void AdJustUp(Heap* obj) { size_t child = obj->size-1; size_t parent = (child - 1) / 2; while (child) { if (obj->data[parent] > obj -> data[child]) { HPDataType tmp = obj->data[child]; obj->data[child] = obj->data[parent]; obj->data[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break; } } } void HeapPush(Heap* obj, HPDataType x) { assert(obj); if (obj->size == obj->capacity) { obj->capacity *= 2; HPDataType* tmp = (HPDataType*)realloc(obj->data, obj->capacity*sizeof(HPDataType)); assert(tmp); obj->data = tmp; } obj->data[obj->size] = x; ++obj->size; //进行向下调整以保证堆的格式 AdJustUp(obj); } void HeapPrint(Heap* obj) { for (size_t i = 0; i < obj->size; i++) { printf("%d ", obj->data[i]); } } void AdJustDown(Heap* obj) { size_t father = 0; size_t child = father*2+1; while (child < obj->size) { //选出最小的孩子 if (child+1<obj->size && obj->data[child] > obj->data[child + 1]) { child++; } if (obj->data[child] < obj->data[father]) { HPDataType tmp = obj->data[child]; obj->data[child] = obj->data[father]; obj->data[father] = tmp; father = child; child = father * 2 + 1; } else { break; } } } void HeapPop(Heap* obj) { assert(obj); assert(obj->size > 0); obj->data[0] = obj->data[obj->size - 1]; obj->size--; AdJustDown(obj); } HPDataType HeapTop(Heap* obj) { assert(obj); assert(obj->size); return obj->data[0]; } size_t HeapSize(Heap* obj) { assert(obj); return obj->size; } bool HeapEmpty(Heap* obj) { assert(obj); return obj->size == 0; }
