基础满二叉树定义: 除最后一层没有任何子节点外 每一层节点都有两个子节点数学公式: 层次为h(从0开始) 深度为d(h+1) 节点总数n每一层的节点个数: 2^n节点总数: 2^d -1深度: log2n完全二叉树定义: 除了最后一层外 其他各层节点数都是满的 且最后一层的节点都连续集中在左边二叉堆定义: 二叉树就是满足如下性质的完全二叉树大顶堆: 父节点的值比每个子节点的值要大小顶堆: 父节点的值比每个子节点的值要小特点堆顶永远是最大/最小值 但是其他元素顺序未知堆操作堆上浮: 将节点和父节点进行比较 如果不满足堆条件则和父节点交换 直到满足条件堆下沉: 将节点和子节点比较 找到最符合堆条件的节点和父节点交换 直到满足条件添加元素: 将节点添加到堆尾，然后执行上浮操作，复杂度O(log2n)弹出元素: 交换堆顶和堆尾元素值，然后弹出堆尾，复杂度O(log2n)获取堆顶元素值: 复杂度O(1)用途作为优先级队列堆排序 复杂度O(logn)实现class Heap { protected heapArr: number[]; constructor() { this.heapArr = [0]; // 下标从1开始 } // 交换 private swap(i: number, j: number) { [this.heapArr[j], this.heapArr[i]] = [this.heapArr[i], this.heapArr[j]]; } // 获取左节点索引 private getLeftIndex(i: number) { return 2 * i; } // 获取右节点索引 private getRightIndex(i: number) { return 2 * i + 1; } // 获取父节点索引 private getParentIndex(i: number) { return i >> 1; } // 对比方法-默认小顶堆 protected compare(parentIndex: number, childIndex: number) { return this.heapArr[parentIndex] < this.heapArr[childIndex]; } // 上浮 private shiftUp(i: number) { while (i > 1 && this.compare(this.getParentIndex(i), i) === false) { const parentIndex = this.getParentIndex(i); this.swap(i, parentIndex); // 交换两者的值 i = parentIndex; } } // 下沉/堆化 private shiftDown(i: number) { while (this.getLeftIndex(i) <= this.size) { let childIndex = this.getLeftIndex(i); let rightIndex = this.getRightIndex(i); // 小顶堆下 如果右节点的值更小 则交换右节点 if (rightIndex <= this.size && this.compare(rightIndex, childIndex)) childIndex = rightIndex; if (this.compare(i, childIndex)) return; // 如果值满足条件则跳出循环 this.swap(i, childIndex); // 继续下沉 i = childIndex; } } // 获取堆长度 get size() { return this.heapArr.length - 1; } // 获取堆顶元素 peek() { return this.heapArr[1]; } // 添加元素 push(item: number) { // 添加元素后上浮 this.heapArr.push(item); this.shiftUp(this.size); } // 弹出元素 pop() { if (this.size === 0) return undefined; this.swap(1, this.size); const item = this.heapArr.pop(); this.shiftDown(1); // 下沉 return item; } } // 小顶堆 export class MinHeap extends Heap { protected compare(parentIndex: number, childIndex: number) { return this.heapArr[parentIndex] < this.heapArr[childIndex]; } } // 大顶堆 export class MaxHeap extends Heap { protected compare(parentIndex: number, childIndex: number) { return this.heapArr[parentIndex] > this.heapArr[childIndex]; } }相关题215. 数组中的第K个最大元素给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。 示例: 输入: [3,2,1,5,6,4], k = 2 输出: 5解法: 通过维护一个长度为k的小顶堆，当遍历完所有结果，堆顶就是第k大的值function findKthLargest(nums: number[], k: number): number { const heap = new MinHeap(); for (let num of nums) { heap.push(num); if (heap.size > k) { heap.pop(); } } return heap.peek(); }502. IPO假设 力扣（LeetCode）即将开始IPO。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。 给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。 最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。 总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。 答案保证在 32 位有符号整数范围内。 示例： 输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] 输出：4 解释： 由于你的初始资本为 0，你仅可以从 0 号项目开始。 在完成后，你将获得 1 的利润，你的总资本将变为 1。 此时你可以选择开始 1 号或 2 号项目。 由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。 因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。解决: 通过维护一个大顶堆来获取最大的收益项目，此外这道题还有一个技巧就是通过先将项目进行排序，然后通过维护进度指针来跳过重复项目添加进堆function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number { // 将项目整合成一个数组 let projects = capital.map((v, i) => [v, profits[i]]); projects = projects.sort((a, b) => a[0] - b[0]); // 按照启动资金排序为了不重复添加已做项目 不然每次都要重新获取一次还会重复 // 大顶堆存储项目利润 const maxHeap = new MaxHeap(); // 添加过的项目索引 let currProjectIndex = 0; // 项目次数 for (let i = 0; i < k; i++) { // 获取满足启动资金的项目 for (let j = currProjectIndex; j < profits.length; j++) { if (projects[j][0] <= w) { // 如果满足启动资金则添加到大顶堆 添加索引+1 maxHeap.push(projects[j][1]); currProjectIndex++; } else { // 否则说明当前资金不足以启动资金 直接跳出循环 break; } } // 如果有项目做完增加启动资金 if (maxHeap.size > 0) { w += maxHeap.pop()!; } else { // 没有项目做说明启动资金不够了 直接退出 return w; } } return w; }