堆
1.堆的概念
- 堆中某个结点的值总是不大于或不小于其父结点的值；
- 堆总是一棵齐全二叉树
- 堆能够存储在程序表中，假如父节点下标x，则它的左右孩子下标别离为2x+1、2x+2；若一个节点下标为x，则它的父节点为（x-1)/2
2.堆的实现
typedef int type;typedef struct Heap{ type* a; int size; int capacity;}Heap;void heap_init(Heap* hp){ assert(hp); hp->a = NULL; hp->size = hp->capacity = 0;}void heap_destroy(Heap* hp){ assert(hp); free(hp->a); hp->a = NULL; hp->size = hp->capacity = 0;}//这是小根堆的up nlognvoid heap_small_up(type* a, int x){ int parent = (x - 1) / 2; while (x > 0) { if (a[x] < a[parent]) { heap_swap(&a[x], &a[parent]); x = parent; parent = (x - 1) / 2; } else { break; } }}//这是大根堆的up nlognvoid heap_big_up(type* a, int x){ int parent = (x - 1) / 2; while (x > 0) { if (a[x] > a[parent]) { heap_swap(&a[x], &a[parent]); x = parent; parent = (x - 1) / 2; } else { break; } }}void heap_push(Heap* hp, type x){ assert(hp); if (hp->size == hp->capacity) { //须要扩容 int newcapa = (hp->capacity == 0) ? 4 : 2 * hp->capacity; type* t = (type*)realloc(hp->a,sizeof(type) * newcapa); if (t == NULL) { printf("realloc fail\n"); exit(-1); } hp->a = t; hp->capacity = newcapa; } hp->a[hp->size] = x; ++hp->size; heap_up(hp->a, hp->size - 1);//nlogn}void heap_print(Heap* hp){ assert(hp); for (int i = 0; i < hp->size; ++i) { printf("%d ", hp->a[i]); } printf("\n");}void heap_swap(type* x, type* y){ type t = *x; *x = *y; *y = t;}type heap_top(Heap* hp){ assert(hp); assert(hp->size > 0); return hp->a[0];}void heap_pop(Heap* hp)//删除top元素{ assert(hp); assert(hp->size > 0); heap_swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; heap_down(hp->a,hp->size,0);//O(n)}bool is_empty(Heap* hp){ assert(hp); return hp->size == 0;}int heap_size(Heap* hp){ assert(hp); return hp->size;}//小根堆的下沉 T = nvoid heap_down(type* a,int size, int x){ int child = 2 * x + 1; while (child < size) { if (child+1<size&&a[child + 1] < a[child]) { child++; } if (a[child] < a[x]) { heap_swap(&a[child], &a[x]); x = child; child = 2 * x + 1; } else { break; } }}//大根堆的下沉 T = nvoid heap_down(type* a,int size, int x){ int child = 2 * x + 1; while (child < size) { if (child+1<size&&a[child + 1] > a[child]) { child++; } if (a[child] > a[x]) { heap_swap(&a[child], &a[x]); x = child; child = 2 * x + 1; } else { break; } }}void top_k(int *a, int k,int n)//在N中找最大或者最小的前k个，N>>k{ //N100亿，40G内存能力放下 //eg.找最大的前k个，建设一个k的小堆 //步骤：1.前k个数建设一个小堆；2.剩下的N-k个数字外面，只有数字比堆顶要大，就进入堆； int *kmin = (int*)malloc(sizeof(int)*k); assert(kmin); for(int i=0;i<k;++i) { kmin[i] = a[i]; } for(int i = (k-2)/2;i>=0;--i) { heap_small_down(kmin, k, i); } for(int j = k; k>n; ++k) { if(a[j]>kmin[0]) { kmin[0] = a[j]; heap_small_down(kmin, k, 0); } } }void heap_sort(type* a, int n){ //建堆1.O(nlogn) for (int i = 1; i < n; ++i) { heap_small_up(a, i); } //建堆2.O(n) int i = (n - 2) / 2;//最初一个结点的父亲，就是倒数第一个非叶子结点 for (; i >= 0; --i) { heap_small_down(a, n, i); } //要排升序，如果建设小堆，每次取完头，须要再次建堆。如果每次都是建堆来选数据，那太慢了！(n*n)没有应用到堆的劣势 //所以升序建设大堆,降序建小堆,O(nlogn) int end = n - 1; while (end > 0)//nlogn { heap_swap(&a[0], &a[end]); heap_down(a, end, 0); --end; }}3.链式存储的二叉树实现
typedef struct tree_node{ struct tree_node* l; struct tree_node* r; type data;}node;node* buy_node(type x){ node* newnode = (node*)malloc(sizeof(node)); assert(newnode); newnode->l = newnode->r = NULL; newnode->data = x; return newnode;}void pre_order(node* root){ if (root == NULL) { printf("$ "); return; } printf("%d ", root->data); pre_order(root->l); pre_order(root->r);}void in_order(node* root){ if (root == NULL) { printf("$ "); return; } pre_order(root->l); printf("%d ", root->data); pre_order(root->r);}void post_order(node* root){ if (root == NULL) { printf("$ "); return; } pre_order(root->l); pre_order(root->r); printf("%d ", root->data);}//线程不平安int count = 0;void size1(node* root){ if (root == NULL) { return; } count++; size1(root->l); size1(root->r);}int size2(node* root){ if (root == NULL) { return 0; } return size2(root->l) + size2(root->r) + 1;}//求一棵树有多少叶子int count1 = 0;int lead_size1(node* root){ if (root == NULL) return; if (root->l == NULL && root->r == NULL) count1++; lead_size(root->l); lead_size(root->r);}int lead_size2(node* root){ if (root == NULL)return 0; if (root->l == NULL && root->r == NULL) return 1; return lead_size2(root->l) + lead_size2(root->r);}//求第k层结点的个数int k_num(node* root,int k){ assert(k >= 1); if (root == NULL)return 0; if (k == 1)return 1; return k_num(root->l, k - 1) + k_num(root->r, k - 1);}//求二叉树的深度int deep(node* root){ if (root == NULL)return 0; return deep(root->l) > deep(root->r) ? deep(root->l) + 1 : deep(root->r) + 1;}//求值为x的结点node* find(node* root, type x){ if (root == NULL) return NULL; if (root->data == x) return root; node* ret1 = find(root->l, x); if (ret1)return ret1; node* ret2 = find(root->r, x); if (ret2)return ret2; return NULL;}//二叉树的档次遍历void bfs(node* root){ queue<node*> q; if(root!=NULL)q.push(root); whlie(!q.empty) { node* t = q.top(); q.pop(); printf("%d ", t->data); if (t->l != NULL)q.push(t->l); if (t->r != NULL)q.push(t->r); } printf("\n");}void destroy(node* root){ //应用后序遍历 if (root == NULL)return; destroy(root->l); destroy(root->r); free(root);}//判断一个二叉树是不是齐全二叉树bool is(){ queue<node*> q; if (root != NULL)q.push(root); whlie(!q.empty()) { node* t = q.top(); q.pop(); if (t) { q.push(t->l); q.push(t->r); } else { break; } } while (!q.empty()) { node* t = q.top(); q.pop(); if (t) { q.destroy(); return false; } } q.destroy(); return true; }4.链式存储的二叉树oj
965. 单值二叉树 - 力扣（LeetCode）
//办法一bool f = true;void pre_order(struct TreeNode* root, int val){ if(root == NULL||f==false)return; if(root->val != val) { f = false; return; } pre_order(root->left, val); pre_order(root->right,val);}bool isUnivalTree(struct TreeNode* root){ if(root==NULL)return true; f = true; pre_order(root,root->val); if(f)return true; return false;} //办法二bool isUnivalTree(struct TreeNode* root){ if(root==NULL)return true; if(root->left&&root->val != root->left->val)return false; if(root->right&&root->right->val!=root->val)return false; return isUnivalTree(root->left)&&isUnivalTree(root->right) } 100. 雷同的树 - 力扣（LeetCode）
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p==NULL &&q==NULL)return true; if(p==NULL ||q==NULL)return false; if(p->val != q->val)return false; return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}101. 对称二叉树 - 力扣（LeetCode）
bool is(struct TreeNode* p,struct TreeNode* q){ if(p==NULL &&q==NULL)return true; if(p==NULL ||q==NULL)return false; if(p->val != q->val)return false; return is(p->left,q->right)&&is(p->right,q->left);} bool isSymmetric(struct TreeNode* root){ if(root == NULL)return true; return is(root->left,root->right);}572. 另一棵树的子树 - 力扣（LeetCode）
bool issame(struct TreeNode* p, struct TreeNode* q){ if(p==NULL &&q==NULL)return true; if(p==NULL ||q==NULL)return false; if(p->val != q->val)return false; return issame(p->left,q->left)&&issame(p->right,q->right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(root == NULL)return false; if(issame(root, subRoot))return true; return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}144. 二叉树的前序遍历 - 力扣（LeetCode）
vector<int>ans;class Solution {public: void pre_order(TreeNode* root) { if(root== NULL)return; ans.push_back(root->val); pre_order(root->left); pre_order(root->right); } vector<int> preorderTraversal(TreeNode* root) { ans.clear(); pre_order(root); return ans; }};二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
typedef char type;typedef struct tree_node{ struct tree_node* l; struct tree_node* r; type data;}node;node* buy_node(type x){ node* newnode = (node*)malloc(sizeof(node)); assert(newnode); newnode->l = newnode->r = NULL; newnode->data = x; return newnode;}node*create(char*str, int*pi){ if(str[*pi]=='#') { ++(*pi); return NULL; } node* root = buy_node(str[(*pi)++]); root->l = create(str, pi); root->r = create(str, pi); return root;}void in_order(node*root){ if(root==NULL)return; in_order(root->l); printf("%c ",root->data); in_order(root->r);}int main() { char str[100]; scanf("%s",str); int i = 0; node*root = create(str, &i); in_order(root); return 0;}