首页 > 程序开发 > 软件开发 > 其他 >

堆的详情介绍

2018-02-18

堆的详情介绍。分金条:一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?

优先级队列就是堆

分金条

一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的
金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金
条,怎么分最省铜板?
例如,给定数组{10,20,30},代表一共三个人,整块金条长度为10+20+30=60.
金条要分成10,20,30三个部分。
如果,
先把长度60的金条分成10和50,花费60
再把长度50的金条分成20和30,花费50
一共花费110铜板。
但是如果,
先把长度60的金条分成30和30,花费60
再把长度30金条分成10和20,花费30
一共花费90铜板。
输入一个数组的长度
数组内各个元素的值 ,返回分割的最小代价。

这道题仔细观察后其实就是哈弗曼树,将权值累加就是答案,和上一篇博客的题一模一样,甚至代码都不用改。

import java.util.PriorityQueue;
import java.util.Scanner;

public class 分金条 {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        PriorityQueue heap=new PriorityQueue();
        for (int i = 0; i < n; i++) {
            heap.add(input.nextInt());
        }
        int sum=0;
        while(heap.size()>1){
            int temp=heap.poll()+heap.poll();
            sum+=temp;
            heap.add(temp);
        }
        System.out.println(sum);
//      while (!heap.isEmpty()) {
//          System.out.println(heap.poll());
//      }
    }

}

堆最重要的两个操作

HeapInsert
插入,这是构建堆的操作

Heapfy
这是取出堆顶元素后,堆调整的过程。

在一些竞赛和面试题中还需要你具有改写堆结构的能力。

堆的表示

堆是一棵完全二叉树的结构,用数组就能很好的表示
下标为i的节点
左孩子节点下标为2*i+1 右孩子节点下标为2*i+2
下标为i的节点
父节点为(i-1)/2 整型的除法

输出前n个最大数

java中的PriorityQueue默认是小顶堆。如需改写成大顶堆需要传一个比较器参数
给你n个整数,请按照从大到小输出其中前m个大的数
输入
每组测试数据有两行,第一行有两个数n,m(0 < n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000],的整数。
输出
从大到小输出前m大的数
输入
5 3
3 -35 92 213 -644
输出
213 92 3
三种方法

数组排序,然后输出
最好的快排,时间复杂度O(N*logN) 空间复杂度O(logN)
显然题目不是考察你排序,假设我输入数组长度10000我只要前两个最大的数,那么只需两次遍历 时间复杂度O(m
*n) 就可以得出 但是排序的时间复杂度O(N*logN),如果排序需要把数组整体有序,代价太大,而且是无效代价。

类Hash的思想
开辟100 0000长度的数组,因为题意说明了,每个元素数值各不相同,那么在输入的时候只需要输入数作为下标,找到那个位置,然后打上标记,找的时候只需要从后往前遍历,把遇到的前n个有标记的数打印即可。
分析:时间复杂度O(n) 空间复杂度 O(1000000)其实这个不是常数项,是和数据规模有关的 应该是O(n)
但是限制比较多,一个是数据规模,另一个是不允许重复

建立大根堆,然后弹出m个元素。建堆时间复杂度O(n) 空间复杂度O(n) 调整堆时间复杂度(logN)
这种方法可以接受相同元素

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 输出前n个最大数 {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int x=input.nextInt();
        if (x>n) {
            return;
        }
        int temp;
        PriorityQueue heap=new PriorityQueue(new MyCmp()); 
        for (int i = 0; i < n; i++) {
            temp=input.nextInt();   
            heap.add(temp);
        }
        for (int i=0;i

改写堆结构

随时找到数据流的中位数 【题目】 有一个源源不断地吐出整数的数据流,假设你有足够的空间来 保存吐出的数。请设计一个名叫MedianHolder的结构, MedianHolder可以随时取得之前吐出所有数的中位数。 【要求】 1.如果MedianHolder已经保存了吐出的N个数,那么任意时刻 将一个新数加入到MedianHolder的过程,其时间复杂度是 O(logN)。 2.取得已经吐出的N个数整体的中位数的过程,时间复杂度为 O(1)。

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MadianQuick {

    public static class MedianHolder {
        //n/2大根堆 n/2小根堆
        private PriorityQueue maxHeap = new PriorityQueue(new MaxHeapComparator());
        private PriorityQueue minHeap = new PriorityQueue(new MinHeapComparator());

        private void modifyTwoHeapsSize() {
            if (this.maxHeap.size() == this.minHeap.size() + 2) {
                this.minHeap.add(this.maxHeap.poll());
            }
            if (this.minHeap.size() == this.maxHeap.size() + 2) {
                this.maxHeap.add(this.minHeap.poll());
            }
        }

        public void addNumber(int num) {
            if (this.maxHeap.isEmpty()) {
                this.maxHeap.add(num);
                return;
            }
            if (this.maxHeap.peek() >= num) {
                this.maxHeap.add(num);
            } else {
                if (this.minHeap.isEmpty()) {
                    this.minHeap.add(num);
                    return;
                }
                if (this.minHeap.peek() > num) {
                    this.maxHeap.add(num);
                } else {
                    this.minHeap.add(num);
                }
            }
            modifyTwoHeapsSize();
        }

        public Integer getMedian() {
            int maxHeapSize = this.maxHeap.size();
            int minHeapSize = this.minHeap.size();
            if (maxHeapSize + minHeapSize == 0) {
                return null;
            }
            Integer maxHeapHead = this.maxHeap.peek();
            Integer minHeapHead = this.minHeap.peek();
            if (((maxHeapSize + minHeapSize) & 1) == 0) {
                return (maxHeapHead + minHeapHead) / 2;
            }
            return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
        }

    }

    public static class MaxHeapComparator implements Comparator {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 > o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static class MinHeapComparator implements Comparator {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 < o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    // for test, this method is ineffective but absolutely right
    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 200000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            MedianHolder medianHold = new MedianHolder();
            for (int j = 0; j != arr.length; j++) {
                medianHold.addNumber(arr[j]);
            }
            if (medianHold.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");

    }

}
相关文章
最新文章
热点推荐