二叉树大(小)堆以及堆排序

1. 堆的概念以及特性

如果有一个数的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆 性质 1.堆中某个节点的值总是不大于或不小于其父节点的值； 2.堆总是一棵完全二叉树

2. 小堆的实现：

实现大堆转换向上调整和向下调整条件即可

#pragma once #include "assert.h" #include <stdio.h> #include<stdlib.h> typedef int HPDataType; typedef struct Heap { HPDataType* _array; int _capacity; int _size; }Heap; void Swap(HPDataType *a, HPDataType *b) { HPDataType tmp = *a; *a = *b; *b = tmp; } //向下调整 void AdjustDown(Heap* hp,int size,int root) { assert(hp); int child = root * 2 + 1; while (child < size) { if (((child + 1) < size) && (hp->_array[child + 1] < hp->_array[child])) { child = child + 1; } if ((hp->_array[root]) > (hp->_array[child])) { Swap(&(hp->_array[root]), &(hp->_array[child])); root = child; child = root * 2 + 1; } else { return; } } } //向上调整 void AdjustUp(Heap* hp, int size, int child) { int parent = (child-1) / 2; while (parent >= 0 && child != 0) { if (hp->_array[parent] > hp->_array[child]) { Swap(&(hp->_array[parent]), &(hp->_array[child])); } child = parent; parent = (child-1) / 2; } } // 用数组初始化堆 void InitHeap(Heap* hp, HPDataType* array, int size) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (hp->_array == NULL) { assert(hp->_array); return; } for (int i = 0; i < size; i++) { hp->_array[i] = array[i]; } hp->_capacity = size; hp->_size = size; int root = size / 2; for(;root >=0;--root) AdjustDown(hp,size,root); } // 初始化一个空堆 void InitEmptyHeap(Heap* hp, int capacity) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*capacity); if (hp->_array == NULL) { assert(hp->_array); return; } hp->_size = 0; hp->_capacity = capacity; } // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, HPDataType data) { assert(hp); if (hp->_size == hp->_capacity) { hp->_capacity += hp->_capacity; hp->_array = (HPDataType*)realloc(hp->_array, hp->_capacity * sizeof(HPDataType)); if (hp->_array == NULL) { assert(0); return; } } hp->_array[hp->_size] = data; hp->_size++; AdjustUp(hp,hp->_size,hp->_size - 1); } // 删除堆顶元素 void EraseHeap(Heap* hp) { assert(hp); if (hp->_size == 0) { return; } Swap(&(hp->_array[0]), &(hp->_array[hp->_size - 1])); hp->_size--; AdjustDown(hp,hp->_size,0); } // 获取堆中有效元素个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 检测堆是否为空堆 int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; } // 获取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); if (hp->_size == 0) { return NULL; } return hp->_array[hp->_size - 1]; } // 销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_array = NULL; hp->_size = 0; hp->_capacity = 0; } } void HeadTest() { Heap hp; int a[] = {6,5,4,3,2,1}; InitHeap(&hp, a, sizeof(a) / sizeof(a[0])); InsertHeap(&hp, 0); }

3. 可以控制创建大堆还是小堆

typedef int HPDataType; typedef int(*PCOM)(HPDataType, HPDataType); // 堆中元素进行小于比较 int Less(HPDataType left, HPDataType right) { return left < right; } // 堆中元素进行大于比较 int Greater(HPDataType left, HPDataType right) { return left > right; } typedef struct Heap { HPDataType* _array; int _capacity; int _size; PCOM Compare; // 函数指针变量，保存用户传递的比较中堆中元素方法 }Heap; void Swap(HPDataType *a, HPDataType *b) { HPDataType tmp = *a; *a = *b; *b = tmp; } //向下调整 void AdjustDown(Heap* hp,int size,int root, PCOM compare) { assert(hp); int child = root * 2 + 1; while (child < size) { if (((child + 1) < size) && compare(hp->_array[child + 1] ,hp->_array[child])) { child = child + 1; } if (compare(hp->_array[child] ,hp->_array[root])) { Swap(&(hp->_array[root]), &(hp->_array[child])); root = child; child = root * 2 + 1; } else { return; } } } //向上调整 void AdjustUp(Heap* hp, int size, int child, PCOM compare) { int parent = (child-1) / 2; while (parent >= 0 && child != 0) { if (compare(hp->_array[child] ,hp->_array[parent])) { Swap(&(hp->_array[parent]), &(hp->_array[child])); } child = parent; parent = (child-1) / 2; } } // 用数组初始化堆 void InitHeap(Heap* hp, HPDataType* array, int size, PCOM compare) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (hp->_array == NULL) { assert(hp->_array); return; } for (int i = 0; i < size; i++) { hp->_array[i] = array[i]; } hp->_capacity = size; hp->_size = size; int root = size / 2; for(;root >=0;--root) AdjustDown(hp,size,root,compare); } // 初始化一个空堆 void InitEmptyHeap(Heap* hp, int capacity, PCOM compare) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*capacity); if (hp->_array == NULL) { assert(hp->_array); return; } hp->_size = 0; hp->_capacity = capacity; } // 在堆中插入值为data的元素 void InsertHeap(Heap* hp, HPDataType data, PCOM compare) { assert(hp); if (hp->_size == hp->_capacity) { hp->_capacity += hp->_capacity; hp->_array = (HPDataType*)realloc(hp->_array, hp->_capacity * sizeof(HPDataType)); if (hp->_array == NULL) { assert(0); return; } } hp->_array[hp->_size] = data; hp->_size++; AdjustUp(hp,hp->_size,hp->_size - 1, compare); } // 删除堆顶元素 void EraseHeap(Heap* hp,PCOM compare) { assert(hp); if (hp->_size == 0) { return; } Swap(&(hp->_array[0]), &(hp->_array[hp->_size - 1])); hp->_size--; AdjustDown(hp,hp->_size,0,compare); } // 获取堆中有效元素个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 检测堆是否为空堆 int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; } // 获取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); if (hp->_size == 0) { return NULL; } return hp->_array[hp->_size - 1]; } // 销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_array = NULL; hp->_size = 0; hp->_capacity = 0; } } void HeadTest() { Heap hp; int a[] = {6,5,4,3,2,1}; InitHeap(&hp, a, sizeof(a) / sizeof(a[0]),Less); InsertHeap(&hp, 0,Less); }

4.堆排序

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

5.TOP K 问题

分析：时间复杂度为O（n*logn），时间复杂度非常高，因为要对整个数组进行排序。 求前K大的元素建立小堆

void Swap(HPDatatype* pLeft, HPDatatype* pRight) { HPDatatype tmp = *pLeft; *pLeft = *pRight; *pRight = tmp; } void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { //用child标记左右孩子中较小的孩子 if (child + 1 < size&&array[child + 1] < array[child]) child += 1; if (array[parent] > array[child]) { Swap(&array[parent], &array[child]); parent = child; child = parent * 2 + 1; } else return; } } void HeapTopk(int*str, int K, int N) { //申请一段空间用来保存str数组中前K个元素 int* array = (int*)malloc(sizeof(int)*K); if (array == NULL) { assert(0); return; } for (int i = 0; i < K; ++i) { array[i] = str[i]; } //建一个小堆 //找倒数第一个非叶子节点 int root = ((K - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, K, root); //遍历比较其余元素 for (int i = 0; i < N - K; ++i) { if (array[0] < str[K + i]) { array[0] = str[K + i]; HeapAdjust(array, K, 0); } } } //测试代码 int main() { int str[] = { 2,7,9,12,3,6,1,5,4,10 }; HeapTopk(str, 4, sizeof(str) / sizeof(str[0]));

求前K小的元素建立大堆

vector<int>res; void HeadAdjust(int *arr, int root, int size); void HeadTopK(vector<int> input, int k); vector<int> GetLeastNumbers_Solution(vector<int> input, int k); vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { if (input.size() < k) return input; HeadTopK(input, k); return res; } void HeadTopK(vector<int> input, int k) { int* arr = new int[k]; for (int i = 0; i < k; i++) arr[i] = input[i]; int root = (k - 2) / 2; for (; root>=0; root--) HeadAdjust(arr, root, k); for (int i = 0; i < input.size() - k; i++) { if (arr[0] > input[k + i]) { arr[0]=input[k + i]; HeadAdjust(arr, 0, k); } } for (int i = 0; i < k; i++) { res.push_back(arr[i]); } delete[] arr; } void HeadAdjust(int *arr, int root, int size) { int child = root * 2 + 1; while (child < size) { if ((child + 1) < size && arr[child] < arr[child + 1]) child = child + 1; if (arr[root] < arr[child]) { swap(arr[root], arr[child]); root = child; child = root * 2 + 1; } else return; } } int main() { int arr[] = { 4, 5, 1, 6, 2, 7, 3, 8 }; vector<int> a; vector<int>b(arr,arr+8); a = GetLeastNumbers_Solution(b, 4); return 0; }