大根堆/小根堆(基于二叉树)
根据子节点序号找父节点序号——parent(int k)
根据父节点序号找左右子节点序号——leftChild(int k)、rightChild(int k)
上浮操作——siftUp(int k)
下沉操作——siftDown(int k)
向最大堆中添加一个新元素——add(int val)
将该元素添加到数组末尾,然后进行上浮操作
取到并删除当前堆的最大元素——pollMax()
最大元素即索引为0的,将该元素替换为最后一个元素,然后进行下沉操作
取到当前堆的最大元素——peekMax()
即索引为0的元素
将任意数组堆化——heapify
方式一:不断add元素,当数据量大时,不易操作,不建议
方式二:从最后一个非叶子节点-索引为0的结点依次进行下沉操作,最后一个非叶子节点即最后一个元素的父节点
优先级队列(基于最大堆/最小堆)JDK中内置的PriorityQueue默认是基于最小堆
内置方法
offer()/add()
poll()/remove()
peek()/element()
isEmpty()
自定义优先级
方法一:本类中实现Comparable接口,实现compareTo方法
方法二:新建类,实现Comparator接口,实现compare方法
TopK问题
取大用小(取前k个最大的,则建小根堆)
取小用大(取前k个最小的,建立大根堆)