数据结构手撕--【堆】

 

目录

​编辑

定义结构体：

初始化：

插入数据：

删除：

取堆顶元素：

堆销毁：

 判断堆是否为空：

TopK问题：

---

堆其实是完全二叉树

物理结构：二叉树的层序遍历（顺序存储）

逻辑结构：完全二叉树

定义结构体：

typedef int HPDataType;
typedef struct heap
{HPDataType* a; //数组指针（指向一块空间）int size; //有效数据个数int capacity; //最多可以存的数据个数
}Heap;

初始化：

void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}

插入数据：

放到最后一个 + 向上调整

向上调整：

void AdjustUp(HPDataType* a, int child)//传进来堆空间 和孩子下标----这个是最后一个节点
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] > a[child]){swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity) * 2;HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}hp->a = tmp;hp->capacity = newcapacity;}hp->a[hp->size] = x;size++;//向上调整 --- 向上调整为一个小堆AdjustUp(hp->a, hp->size-1)
}

删除：

 顶部挪到最后一个 + 向下调整

void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1; //左孩子while (child < n){if (child + 1 < size && a[child] > a[child + 1]) //右孩子小于左孩子{++child;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

void HeapPop(Heap* hp) //删除
{assert(hp);assert(!HeapEmpty());swap(&hp->a[hp->size - 1], &hp->a[0]);size--;//向下调整AdjustDown(h[->a, hp->size, 0]);
}

取堆顶元素：

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

堆销毁：

void HeapDestroy(Heap* hp)
{assert(hp);free(hp->a);hp->size = hp->capacity = 0;
}

 判断堆是否为空：

bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;//为空就返回true
}

TopK问题：

void TestTopk()//topk问题,找出n个数中的前k个最大数
{int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;//生成一百万以内的随机数}a[5] = 1000000 + 1;a[1231] = 1000000 + 2;a[531] = 1000000 + 3;a[5121] = 1000000 + 4;a[115] = 1000000 + 5;a[2335] = 1000000 + 6;a[9999] = 1000000 + 7;a[76] = 1000000 + 8;a[423] = 1000000 + 9;a[3144] = 1000000 + 10;PrintTopK(a, n, 10);
}void PrintTopK(int* a, int n, int k)
{//要找最大的k的元素 //1、创建一个k大小的小堆//2、用堆顶元素和其他的n-k个元素比较，如果有比堆顶元素大的 就替换//3、替换完之后进行向下调整Heap hp;HeapInit(&hp);for (int i = 0; i < k; i++){HeapPush(&hp, a[i]);}for (int i = k; i < n; i++){if (a[i] > HeapTop(&hp)){hp.a[0] = a[i];AdjustDown(hp.a, hp.size, 0);}}HeapPrint(&hp);HeapDestroy(&hp);}