まとめ:ヒープ構造

スタック構造は非常に重要です.そこで特にスタック構造に関する知識点を記録します.1.最も重要なスタックソートの問題:javaリファレンスコードは以下の通りです.

package chapter2;

public class P79_heapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);//maxHeap
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);//     ，       
        }
    }

    public static void heapInsert(int[] arr, int index) {//maxHeap
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {//size-->heapSize
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//left+1--->right
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr,int i,int j){
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    public static void main(String[] args) {
        int[] arr={1,3,5,7,9,2,4,6,8};
        heapSort(arr);
        for(int num:arr){
            System.out.print(num+" ");
        }
    }
}

2.ハフマン問題の小根の山.1枚の金棒を半分に切るには、長さの数値と同じ銅板が必要です.例えば、長さが20の金の棒は、どんなに大きな半分に切っても、銅板が20個かかります.一群の人は金の棒全体を分けたいと思っていますが、どうやって最も節約した銅板を分けますか?例えば、所与の配列{10,20,30}は、合計3人を表し、全体の金条の長さは10+20+30=60である.金条は10,20,30の3つの部分に分けられる.もし、長さ60の金の棒を10と50に分け、60を使って長さ50の金の棒を20と30に分け、50を使って合計110銅板を使う.しかし、長さ60の金の棒を30と30に分け、60を使って長さ30の金の棒を10と20に分け、30を使って全部で90銅板を使う.配列を入力し、分割の最小コストを返します.
考え方:入力した配列をすべて小根の山の中に入れて、毎回小さい2つを取って、得られた和は更に山の中に入れて、途中で累積和を記録して、山の中に1つしか残っていないことを知っています.
JAvaリファレンスコードは以下の通りです.

package zuoshen1;

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

public class HuffmanTree {
    public static int lessMoney(int[] arr){
        if(arr==null||arr.length<1)
            throw new RuntimeException("arr is null!");
        PriorityQueue pq=new PriorityQueue<>(new MinheapComparator());//    ，      
        for(int i=0;i1){//==1 break
            cur=pq.poll()+pq.poll();
            sum+=cur;
            pq.add(cur);
        }
        return sum;
    }
    public static class MinheapComparator implements Comparator {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2; // < 0  o1 < o2    
        }

    }

    public static class MaxheapComparator implements Comparator {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1; // <   o2 < o1
        }
    }

    public static void main(String[] args) {
        System.out.println(lessMoney(new int[]{10,20,30}));
    }
}

3.入力:パラメータ1、正数配列costsパラメータ2、正数配列profitsパラメータ3、正数kパラメータ4、正数m costs[i]i番項目の費用profits[i]i番項目が費用を差し引いた後で稼ぐことができるお金(利益)kは、並列にできないことを示し、シリアルにできる最大k個の項目mは、最初の資金説明を示します.すぐに得られる収益は、次のプロジェクトをサポートすることができます.出力:あなたが最後に得た最大金額.
考え方:投資、あなたは現在の資金Wを持っていて、あなたは全部でK回投資することができて、しかも毎回1つしか投資できません.この問題を2つのスタックで解決し,小さなスタックはプロジェクトのcostに基づいて構築され,大きなスタックは各プロジェクトのprofitに基づいて構築される.我々は,小根スタック中のcostが現在のWより小さいプロジェクトを大根スタックに配置し,大根スタックの構築原理に基づいて,大根スタックが空になるまで最大収益を出して投資したり,K個の投資が締め切られたりする.JAvaリファレンスコードは以下の通りです.

package zuoshen1;

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

public class FindMaximizedCapital {
    public static class Node{
        int c;
        int p;
        public Node(int c,int p){
            this.c=c;
            this.p=p;
        }
    }
    public static class MinComparator implements Comparator{
        @Override
        public int compare(Node o1,Node o2){
            return o1.c-o2.c;//min cost
        }
    }
    public static class MaxComparator implements Comparator{
        @Override
        public int compare(Node o1,Node o2){
            return o2.p-o1.p;//max profit
        }
    }
    public static int findMaximizedCapital(int k,int w,int[] cost,int[] profit){
        if(k<0||w<0||cost==null||profit==null||cost.length!=profit.length)
            throw new RuntimeException("run exception!");
        Node[] nodes=new Node[cost.length];
        PriorityQueue minQ=new PriorityQueue<>(new MinComparator());
        PriorityQueue maxQ=new PriorityQueue<>(new MaxComparator());
        for(int i=0;i=cost[i]//w       ，    
                maxQ.add(minQ.poll());
            }
            if(maxQ.isEmpty()){
                return w;
            }
            //else maxQ is not empty!
            w+=maxQ.poll().p;
        }
        return w;
    }

    public static void main(String[] args) {
        int[] cost={5,6,7,8,9,20};
        int[] profit={1,2,3,5,6,10};
        int w=10;
        int k1=4;
        int k2=6;
        System.out.println(findMaximizedCapital(k1,w,cost,profit));
        System.out.println(findMaximizedCapital(k2,w,cost,profit));
    }
}