二叉堆的原理性质和应用

二叉堆的原理性质和应用二叉堆的主要操作就两个sink下沉和swim上浮用以维护二叉堆的性质。二叉堆的主要应用有两个首先是一种很有用的数据结构优先级队列二是堆排序。二叉堆的原理二叉堆就是一种能够动态排序的数据结构。所谓动态排序就是说我们可以不断往数据结构里面添加或删除元素数据结构会自动调整元素的位置使得我们可以有序地从数据结构中读取元素这是一般的排序算法做不到的。能动态排序的常用数据结构其实只有两个一个是优先级队列底层用二叉堆实现另一个是二叉搜索树。二叉搜索树的用途更广泛优先级队列能做的事情二叉搜索树其实都能做。但优先级队列的接口和代码实现相较于二叉搜索树更简单所以一般能用优先级队列解决的问题没必要用二叉搜索树。二叉堆是怎么做到动态排序的呢这就要说到二叉堆这种结构的性质了。二叉堆的性质二叉堆是一种特殊的二叉树这棵二叉树上的任意节点的值都必须大于等于或小于等于其左右子树所有节点的值。如果是大于等于我们称之为大顶堆如果是小于等于我们称之为小顶堆。对于小顶堆每个节点下方的所有节点的值都比它大那么根节点就是整棵树上的最小值。同理大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。二叉堆还有个性质一个二叉堆的左右子堆子树也是一个二叉堆。二叉堆的应用优先级队列常见接口插入元素pq.push(int x)删除堆顶pq.pop()返回堆顶元素pq.top()判空pq.empty()元素个数pq.size()大顶堆和小顶堆的写法默认为大顶堆小顶堆写法priority_queueint, vectorint, greaterint qp;在题目中的应用力扣23 合并k个升序链表给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。思路合并k个有序链表的逻辑类似合并两个有序链表难点在于如何快速得到k个节点中的最小节点接到结果链表上我们就要用到优先级队列这种数据结构把链表节点放入一个最小堆就可以每次获得k个节点中的最小节点。代码class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { if (lists.empty()) return nullptr; // 虚拟头结点 ListNode* dummy new ListNode(-1); ListNode* p dummy; // 优先级队列最小堆 auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp); // 将 k 个链表的头结点加入最小堆 for (ListNode* head : lists) { if (head ! nullptr) { pq.push(head); } } while (!pq.empty()) { // 获取最小节点接到结果链表中 ListNode* node pq.top(); pq.pop(); p-next node; if (node-next ! nullptr) { pq.push(node-next); } // p 指针不断前进 p p-next; } return dummy-next; } };由于这里装的是listNode*所以必须自定义比较器cmp以使用小顶堆。堆排序每次传入一个无序数组需要重新开始建堆heapify函数就是从堆顶向下逐个比较然后一致维护堆的性质。voidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}voidheapify(intarr[],intn,inti){//这里i指目前的堆顶intlargesti;intlsoni*21;intrsoni*22;if(lsonnarr[largest]arr[lson])largestlson;if(rsonnarr[rson]arr[largest])largestrson;if(largest!i){swap(arr[largest],arr[i]);heapify(arr,n,largest);}}voidheap_sort(intarr[],intn){inti;for(in/2-1;i0;i--)//建堆heapify(arr,n,i);for(intin-1;i0;i--){swap(arr[i],arr[0]);heapify(arr,i,0);}}二叉堆的实现二叉堆多数情况是用数组实现而非二叉树主要原因有二第一个原因是链表节点需要一个额外的指针存储相邻节点的地址所以相对数组链表的内存消耗会大一些。第二个原因也是最主要的原因是时间复杂度的问题正常情况下如何拿到二叉树的底层最右侧节点需要层序遍历或递归遍历二叉树时间复杂度是 O(N)如果用数组来模拟二叉树就可以完美解决这个问题在 O(1)时间内找到二叉树的底层最右侧节点。使用数组来模拟二叉树以及相关公式// 父节点的索引 int parent(int node) { return (node - 1) / 2; } // 左子节点的索引 int left(int node) { return node * 2 1; } // 右子节点的索引 int right(int node) { return node * 2 2; }