构造TopRecord结构问题解法

问题描述

请实现如下结构：
        TopRecord{
                public TopRecord(int K) :         构造时事先指定好K的大小，构造后就固定不变了
                public void add(String str) :         向该结构中加入一个字符串，可以重复加入
                public List top() :         返回之前加入的所有字符串中，词频最大的K个
        }
要求：
        add方法，复杂度O(log K);
        top方法，复杂度O(K)

思路

        Node类，把字符串以及其出现的次数进行封装。

        在TopRecord类中定义了四个变量，分别为Node数组heap用于表示小根堆（固定大小）、heapSize表示小根堆此时里面装的数据数量、strNodeMap表示字符串与Node节点的对应关系，即词频表、nodeIndexMap表示小根堆中Node节点在堆中的位置，若节点不在小根堆中则对应关系的value值用-1表示。

        TopRecord方法对小根堆的大小进行固定。

        add方法流程：

1.         任意添加一个字符串时，我们首先把它在小根堆对应表nodeIndexMap的值preIndex统一固定为-1。
2.         我们查询词频表strNodeMap看该字符串之前是否有过，若之前没有进来过，初始化该字符串的Node，把Node的times值设置为1，放入词频表strNodeMap，设置该节点小根堆对应关系xMap中的对应关系设置为-1，这时的preIndex任然保持-1不变。若之前来过我们在词频表strNodeMap取出对应字符串的Node，查询出该node的词频并加一，在对应关系nodeIndexMap中查找出节点在小根堆中的位置赋值给preIndex。
3.         此时我们查看preIndex的是否为-1既可以判断出该节点现在是否在小根堆上（若为-1表示节点不在小根堆上）。若preIndex不为-1即为节点在小根堆上，此时我们需要从preIndex到 heapSize的位置heapify调整小根堆。若preIndex为-1，分为两种情况：一种是小根堆未满，另一种是小根堆满了。对于小根堆未满情况，我们把该节点放在小根堆最后的位置，记录此时节点在小根堆中的对应关系，从该位置开始向上调整堆heapInsert。

         top方法：此时小根堆中的Node节点即为加入的所有字符串中，词频最大的K个。

        注意：我们在heapify方法和heapInsert方法中交换两个数字位置的时候，我们同时也需要交换heapInsert表中小根堆位置的对应表中的信息。

代码  

    public static class Node {
        public String str;
        public int times;
 
        public Node(String s, int t) {
            str = s;
            times = t;
        }
    }
 
    public static class TopKRecord {
        private Node[] heap;
        private int heapSize;
        private HashMap strNodeMap;
        private HashMap nodeIndexMap;
 
        public TopKRecord(int K) {
            heap = new Node[K];
            heapSize = 0;
            strNodeMap = new HashMap<>();
            nodeIndexMap = new HashMap<>();
        }
 
        public void add(String str) {
            Node curNode = null;
            int preIndex = -1;//str之前在堆上的位置
 
            //查询词频表，看看有没有关于这个str的记录
            if (!strNodeMap.containsKey(str)) {
                curNode = new Node(str, 1);
                strNodeMap.put(str, curNode);
                nodeIndexMap.put(curNode, -1);
            } else {//str之前进来过
                curNode = strNodeMap.get(str);
                curNode.times++;
                preIndex = nodeIndexMap.get(curNode);
            }
            //词频表修改完毕
            if (preIndex == -1) {//不在堆上
                if (heapSize == heap.length) {//堆满了
                    if (heap[0].times < curNode.times) {
                        nodeIndexMap.put(heap[0], -1);
                        nodeIndexMap.put(curNode, 0);
                        heap[0] = curNode;
                        heapify(0, heapSize);
                    }
                } else {//堆没有满
                    nodeIndexMap.put(curNode, heapSize);
                    heap[heapSize] = curNode;
                    heapInsert(heapSize++);
                }
            } else {//str已经在堆上
                heapify(preIndex, heapSize);
            }
        }
 
        public void printTopK() {
            System.out.println("TOP: ");
            for (int i = 0; i != heap.length; i++) {
                if (heap[i] == null) {
                    break;
                }
                System.out.print("Str: " + heap[i].str);
                System.out.println(" Times: " + heap[i].times);
            }
        }
 
        private void heapInsert(int index) {
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (heap[index].times < heap[parent].times) {
                    swap(parent, index);
                    index = parent;
                } else {
                    break;
                }
            }
        }
 
        private void heapify(int index, int heapSize) {
            int l = index * 2 + 1;
            int r = index * 2 + 2;
            int smallest = index;
            while (l < heapSize) {
                if (heap[l].times < heap[index].times) {
                    smallest = l;
                }
                if (r < heapSize && heap[r].times < heap[smallest].times) {
                    smallest = r;
                }
                if (smallest != index) {
                    swap(smallest, index);
                } else {
                    break;
                }
                index = smallest;
                l = index * 2 + 1;
                r = index * 2 + 2;
            }
        }
 
        private void swap(int index1, int index2) {
            nodeIndexMap.put(heap[index1], index2);
            nodeIndexMap.put(heap[index2], index1);
            Node tmp = heap[index1];
            heap[index1] = heap[index2];
            heap[index2] = tmp;
        }
    }