大顶堆定义:父节点要比任意两个孩子的值要大
heapify()建堆之后:
过程:威廉姆斯建堆算法 n*log(n)
这个时间复杂度如何估算呢?
得到这样一个式子以后我们就可以开始算时间复杂度了,但是这似乎有点为难数学不好的同学,但是没有关系!我们可以用这个网站
Wolfram|Alpha：计算型智能 (wolframalpha.com)
输入:
Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]
高度为4 ==>2^4 - 4 -1 = 11 意思是交换11次就能建堆
算法实现:
这个建堆操作要非常熟练!
import java.util.Arrays;
/**
* 大顶堆
*/
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int[] array){
this.array = array;
this.size = array.length;
heapify();
}
public MaxHeap(int capacity){
this.array = new int[capacity];
}
//建堆
private void heapify(){
//如何找到最后这个非叶子节点 这个有公式:size>>1-1 or (size/2-1)
for(int i = size/2-1;i>=0;i--){
down(i);
}
}
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
return 0;
}
//将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
private void down(int parent){
int left = parent*2+1;
int right = left+1;
int max = parent;
if(left<size && array[left]>array[max]){
max = left;
}
if(right<size && array[right]>array[max]){
max = right;
}
if(max!=parent){//找到更大的孩子
swap(max,parent);
down(max);
}
}
//交换两个索引处的元素
private void swap(int i,int j){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6,7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));
//[7, 5, 6, 4, 2, 1, 3]
}
}
填充剩余代码:
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
int top = array[0];
swap(0,size-1);
size--;
down(0);
return top;
}
/**
* 替换堆顶元素
* @param replaced - 新元素
*/
public void replace(int replaced){
array[0] = replaced;
down(0);
}
import java.util.Arrays;
/**
* 大顶堆
*/
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int[] array){
this.array = array;
this.size = array.length;
heapify();
}
public MaxHeap(int capacity){
this.array = new int[capacity];
}
//建堆
private void heapify(){
//如何找到最后这个非叶子节点 这个有公式:size>>1-1 or (size/2-1)
for(int i = size/2-1;i>=0;i--){
down(i);
}
}
/**
* 删除堆顶元素
* @return:堆顶元素
*/
public int peek(){
//当然如果这个堆里面没有数据的话 会报错
//这个可以抛异常
return array[0];
}
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
int top = array[0];
swap(0,size-1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
* @param:index - 索引
* @return:被删除元素
*/
public int poll(int index){
//可以一下考虑 堆为空的时候,这里就先不写了
int deleted = array[index];
swap(index,size-1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
* @param replaced - 新元素
*/
public void replace(int replaced){
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
* @param:offered-新元素
* @return:是否添加成功
*/
public boolean offer(int offered){
if(size==array.length){
return false;
}
up(offered);
size++;
return true;
}
//将 offered元素上浮:直到offered小于父元素或到堆顶
private void up(int offered){
int child = size;
while(child>0){
int parent = (child-1)/2;
if(offered>array[parent]){
array[child] = array[parent];
}else{
break;
}
child = parent;
}
array[child]=offered;
}
//将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
private void down(int parent){
int left = parent*2+1;
int right = left+1;
int max = parent;
if(left<size && array[left]>array[max]){
max = left;
}
if(right<size && array[right]>array[max]){
max = right;
}
if(max!=parent){//找到更大的孩子
swap(max,parent);
down(max);
}
}
//交换两个索引处的元素
private void swap(int i,int j){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6,7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));
//[7, 5, 6, 4, 2, 1, 3]
}
}
堆排序
1.heapify 建立大顶堆
2.将堆顶与堆底交换(最大元素被交换到堆底),缩小并下潜调整堆
3.重复第二步直至堆里剩一个元素
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int[] array){
this.array = array;
this.size = array.length;
heapify();
}
public MaxHeap(int capacity){
this.array = new int[capacity];
}
//建堆
private void heapify(){
//如何找到最后这个非叶子节点 这个有公式:size>>1-1 or (size/2-1)
for(int i = size/2-1;i>=0;i--){
down(i);
}
}
/**
* 删除堆顶元素
* @return:堆顶元素
*/
public int peek(){
//当然如果这个堆里面没有数据的话 会报错
//这个可以抛异常
return array[0];
}
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
int top = array[0];
swap(0,size-1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
* @param:index - 索引
* @return:被删除元素
*/
public int poll(int index){
//可以一下考虑 堆为空的时候,这里就先不写了
int deleted = array[index];
swap(index,size-1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
* @param replaced - 新元素
*/
public void replace(int replaced){
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
* @param:offered-新元素
* @return:是否添加成功
*/
public boolean offer(int offered){
if(size==array.length){
return false;
}
up(offered);
size++;
return true;
}
//将 offered元素上浮:直到offered小于父元素或到堆顶
private void up(int offered){
int child = size;
while(child>0){
int parent = (child-1)/2;
if(offered>array[parent]){
array[child] = array[parent];
}else{
break;
}
child = parent;
}
array[child]=offered;
}
//将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
private void down(int parent){
int left = parent*2+1;
int right = left+1;
int max = parent;
if(left<size && array[left]>array[max]){
max = left;
}
if(right<size && array[right]>array[max]){
max = right;
}
if(max!=parent){//找到更大的孩子
swap(max,parent);
down(max);
}
}
//交换两个索引处的元素
private void swap(int i,int j){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] array = {2,3,1,7,6,4,5};
MaxHeap heap = new MaxHeap(array);
System.out.println(Arrays.toString(heap.array));//[7, 6, 5, 3, 2, 4, 1]
while(heap.size>1){
heap.swap(0,heap.size-1);
heap.size--;
heap.down(0);
}
System.out.println(Arrays.toString(heap.array));//
//[1, 2, 3, 4, 5, 6, 7]
}
}
215. 数组中的第K个最大元素 - 力扣（LeetCode）
先来看看思路:
这里使用小顶堆来解决这个问题,为什么不是大顶堆 咱们往后看
示例一:求第k大 我们可以先把数组前两个放进小顶堆中
实例二:求第k=4大,我们可以先把数组前四个小顶堆中(当然了大顶堆也可以 但是这里用小顶堆)
如果新加进来的元素比堆中的元素逗都小,那么我们什么也不做
如果进来的元素大就替换掉堆顶元素
例子:比如实例1中第三个元素是1 所以咱们什么也不做 接着看下一个数字5,发现5比堆顶元素2大,那么就要进行替换,然后重新调整小顶堆
经过这些运算,小顶堆中就是两个最大的元素 最终返回堆顶元素即可.
public class MinHeap {
int[] array;
int size;
public MinHeap(int[] array){
this.array = array;
this.size = array.length;
heapify();
}
public MinHeap(int capacity){
this.array = new int[capacity];
}
//建堆
private void heapify(){
//如何找到最后这个非叶子节点 这个有公式:size>>1-1 or (size/2-1)
for(int i = size/2-1;i>=0;i--){
down(i);
}
}
/**
* 删除堆顶元素
* @return:堆顶元素
*/
public int peek(){
//当然如果这个堆里面没有数据的话 会报错
//这个可以抛异常
return array[0];
}
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
int top = array[0];
swap(0,size-1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
* @param:index - 索引
* @return:被删除元素
*/
public int poll(int index){
//可以一下考虑 堆为空的时候,这里就先不写了
int deleted = array[index];
swap(index,size-1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
* @param replaced - 新元素
*/
public void replace(int replaced){
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
* @param:offered-新元素
* @return:是否添加成功
*/
public boolean offer(int offered){
if(size==array.length){
return false;
}
up(offered);
size++;
return true;
}
//将 offered元素上浮:直到offered小于父元素或到堆顶
private void up(int offered){
int child = size;
while(child>0){
int parent = (child-1)/2;
if(offered<array[parent]){
array[child] = array[parent];
}else{
break;
}
child = parent;
}
array[child]=offered;
}
//将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
private void down(int parent){
int left = parent*2+1;
int right = left+1;
int min = parent;
if(left<size && array[left]<array[min]){
min = left;
}
if(right<size && array[right]<array[min]){
min = right;
}
if(min!=parent){//找到更大的孩子
swap(min,parent);
down(min);
}
}
//交换两个索引处的元素
private void swap(int i,int j){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
/**
* 求数组中第K大的元素
* 解题思路:
* 1.向小顶堆放入前k个元素
* 2.剩余元素
*
* 若<=堆顶元素,则略过
* 若>堆顶元素,则替换堆顶元素
*
* 3.这样小顶堆始终保留的是到目前为止,第K大的元素
* 4.循环结束,堆顶元素即为第K大元素
*/
public class E02Leetcode215 {
public int findthLargest(int[] numbers,int k){
MinHeap heap = new MinHeap(k);
for (int i = 0; i < k; i++) {
heap.offer(numbers[i]);
}
for (int i = k; i < numbers.length; i++) {
if(numbers[i] > heap.peek()){
heap.replace(numbers[i]);
}
}
return heap.peek();
}
public static void main(String[] args){
//应为5
System.out.println(new E02Leetcode215().findthLargest(new int[]{3,2,1,5,6,4},2));
//应为4
System.out.println(new E02Leetcode215().findthLargest(new int[]{3,2,3,1,2,4,5,5,6},4));
}
}
703. 数据流中的第 K 大元素 - 力扣（LeetCode）
跟上面那倒题目的区别是:上面的数据是固定的 而这题反之
在数组中用堆排序并不是最优的选择因为有更优秀的算法.但是对于这道题目,最好的选择就是使用堆了.
public class MinHeap {
int[] array;
int size;
public MinHeap(int[] array){
this.array = array;
this.size = array.length;
heapify();
}
public MinHeap(int capacity){
this.array = new int[capacity];
}
//建堆
private void heapify(){
//如何找到最后这个非叶子节点 这个有公式:size>>1-1 or (size/2-1)
for(int i = size/2-1;i>=0;i--){
down(i);
}
}
/**
* 删除堆顶元素
* @return:堆顶元素
*/
public int peek(){
//当然如果这个堆里面没有数据的话 会报错
//这个可以抛异常
return array[0];
}
/**
* 删除堆顶元素
* @Returns:堆顶元素
*/
public int poll(){
int top = array[0];
swap(0,size-1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
* @param:index - 索引
* @return:被删除元素
*/
public int poll(int index){
//可以一下考虑 堆为空的时候,这里就先不写了
int deleted = array[index];
swap(index,size-1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
* @param replaced - 新元素
*/
public void replace(int replaced){
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
* @param:offered-新元素
* @return:是否添加成功
*/
public boolean offer(int offered){
if(size==array.length){
return false;
}
up(offered);
size++;
return true;
}
//将 offered元素上浮:直到offered小于父元素或到堆顶
private void up(int offered){
int child = size;
while(child>0){
int parent = (child-1)/2;
if(offered<array[parent]){
array[child] = array[parent];
}else{
break;
}
child = parent;
}
array[child]=offered;
}
//将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
private void down(int parent){
int left = parent*2+1;
int right = left+1;
int min = parent;
if(left<size && array[left]<array[min]){
min = left;
}
if(right<size && array[right]<array[min]){
min = right;
}
if(min!=parent){//找到更大的孩子
swap(min,parent);
down(min);
}
}
public boolean isFull(){
return size==array.length;
}
//交换两个索引处的元素
private void swap(int i,int j){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
public class E03Leetcode703 {
//将小顶堆MinHeap作为成员变量
private MinHeap heap;
public E03Leetcode703(int k,int[] nums){
heap = new MinHeap(k);
for(int num:nums){
add(num);
}
}
//此方法会被不断调用,模拟数据流中新来的元素
public int add(int val){
if(!heap.isFull()){
heap.offer(val);
}
//这样写有些测试样例过不了 因为这是一个流 有可能数组中刚刚开始凑不满三个
//所以我们可以在小顶堆实现ifFull()
else if(val>heap.peek()){
heap.replace(val);
}
return heap.peek();
}
public static void main(String[] args){
E03Leetcode703 test = new E03Leetcode703(3,new int[]{4,5,8,2});
//小顶堆 4 5 8
//跟上一题思路类似
//因为k = 3 所以 4 5 8添加
System.out.println(test.add(3));//[4 5 8] ==>4
System.out.println(test.add(5));//[5,5,8] ==> 5
System.out.println(test.add(10));//[5,8,10] ==> 5
System.out.println(test.add(9));// [8 9 10] ==> 8
System.out.println(test.add(4));// [8 9 10] ==> 8
}
}
295. 数据流的中位数 - 力扣（LeetCode）
可能你会想把数据排序然后就可以求中位数了,但是这是数据流,数据不断变化,这样效率很低
1 2 3 7 8 9
思路:
我们不是说非要把所有的数据收集起来然后重头到尾排个序,我们可以把所有数据分成两部分
一部分是较小的数据 大概占一半 一部分是较大的数据 从小的里面挑大的 大的里面挑小的
s s s g g g
3 7
大顶堆 小顶堆 所以可以用两个堆来解决
import java.util.Arrays;
/**
* <h3>数据流的中位数</h3>
*/
public class E04Leetcode295_1 {
/**
* 为了保证两边数据量的平衡
* <ul>
* <li>两边个数一样时,左边个数加一</li>
* <li>两边个数不一样时,右边个数加一</li>
* </ul>
* 但是, 随便一个数能直接加入吗?
* <ul>
* <li>左边个数加一时, 把新元素加在右边，弹出右边最小的加入左边</li>
* <li>右边个数加一时, 把新元素加在左边，弹出左边最小的加入右边</li>
* </ul>
*/
public void addNum(int num) {
if (left.size() == right.size()) {
right.offer(num);
left.offer(right.poll());
} else {
left.offer(num);
right.offer(left.poll());
}
}
private Heap left = new Heap(10, true);
private Heap right = new Heap(10, false);
@Override
public String toString() {
int size = left.size;
int[] left = new int[size];
for (int i = 0; i < left.length; i++) {
left[size - 1 - i] = this.left.array[i];
}
int[] right = Arrays.copyOf(this.right.array, this.right.size);
return Arrays.toString(left) + " <-> " + Arrays.toString(right);
}
/**
* <ul>
* <li>两边数据一致, 左右各取堆顶元素求平均</li>
* <li>左边多一个, 取左边堆顶元素</li>
* </ul>
*/
public double findMedian() {
if (left.size() == right.size()) {
return (left.peek() + right.peek()) / 2.0;
} else {
return left.peek();
}
}
public static void main(String[] args) {
E04Leetcode295_1 test = new E04Leetcode295_1();
test.addNum(1);
test.addNum(2);
test.addNum(3);
test.addNum(7);
test.addNum(8);
test.addNum(9);
System.out.println(test);
System.out.println(test.findMedian());
test.addNum(10);
System.out.println(test);
System.out.println(test.findMedian());
test.addNum(4);
System.out.println(test);
System.out.println(test.findMedian());
}
}
/**
* 可以扩容的heap max用于指定是大顶堆还是小顶堆
*/
public class Heap {
int[] array;
int size;
boolean max;
public int size() {
return size;
}
public Heap(int capacity, boolean max) {
this.array = new int[capacity];
this.max = max;
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
*/
public void offer(int offered) {
if (size == array.length) {
grow();
}
up(offered);
size++;
}
private void grow() {
int capacity = size + (size >> 1);
int[] newArray = new int[capacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
boolean cmp = max ? offered > array[parent] : offered < array[parent];
if (cmp) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public Heap(int[] array, boolean max) {
this.array = array;
this.size = array.length;
this.max = max;
heapify();
}
// 建堆
private void heapify() {
// 如何找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int min = parent;
if (left < size && (max ? array[left] > array[min] : array[left] < array[min])) {
min = left;
}
if (right < size && (max ? array[right] > array[min] : array[right] < array[min])) {
min = right;
}
if (min != parent) { // 找到了更大的孩子
swap(min, parent);
down(min);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public Object getSize() {
return size;
}
}-----
import java.util.Comparator;
import java.util.PriorityQueue;
/*
当然我们也可以不用自己定义的heap 在java中也有一个功能类似的类PriorityQueue 优先级队列
*/
public class E04Leetcode295 {
/**
* 为了保证两边数据量的平衡
*
* 两边个数一样时,左边个数+1
* 两边个数不一样时,右边个数+1
*
* 但是,随便一个数直接加入吗?
*
* 左边个数+1时,应该挑右边最小的加入
* 右边个数+1时,应该挑左边最大的加入
*
*/
public void addNum(int num){
if(left.size()==right.size()){
right.offer(num);
left.offer(right.poll());
}else{
left.offer(num);
right.offer(left.poll());
}
}
/**
* 两边数据一致,左右各取堆顶元素平均
* 左边多一个,取左边堆顶元素
*/
public double findMedian(){
if(left.size()== right.size()){
return (left.peek()+right.peek())/2.0;
}
else {
return left.peek();
}
}
//大顶堆
private PriorityQueue<Integer> left =new PriorityQueue<>(
(a,b)->Integer.compare(b,a)//-1 b<a 0 a==b 1 b>a
);
//比较器
//小顶堆
private PriorityQueue<Integer> right =new PriorityQueue<>(
(a,b)->Integer.compare(a,b)//省略不写也一样 compare
//-1 a<b 0 a==b 1 a>b
);
public static void main(String[] args) {
//这里就不去看源码了 以上浮为例,大概的实现逻辑
Comparator<Integer>cmp = (a,b)->Integer.compare(a,b);//小顶堆比较器compare -1 a<b,0 a==b,1 a>b
// Comparator<Integer>cmp = (a,b)->Integer.compare(b,a);//小顶堆比较器compare -1 b<a,0 a==b,1 b>a
int a = 10;//父元素值
int b =5;//新增元素值
if(cmp.compare(a,b)>0){
System.out.println("上浮");
}else{
System.out.println("停止上浮");
}
}
}
class MedianFinder {
PriorityQueue<Integer> queMin;
PriorityQueue<Integer> queMax;
public MedianFinder() {
queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
}
public void addNum(int num) {
if (queMin.isEmpty() || num <= queMin.peek()) {
queMin.offer(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.offer(queMin.poll());
}
} else {
queMax.offer(num);
if (queMax.size() > queMin.size()) {
queMin.offer(queMax.poll());
}
}
}
public double findMedian() {
if (queMin.size() > queMax.size()) {
return queMin.peek();
}
return (queMin.peek() + queMax.peek()) / 2.0;
}
}