1 堆
1.1 堆結構
- 堆是用數組實現的完全二叉樹結構
- 完全二叉樹中如果每棵樹的最大值都在頂部就是大根堆,最小值在頂部就是小根堆
- 堆結構的
heapInsert
就是插入操作,heapify
是取出數組后進行堆結構調整的操作 - 優先級隊列結構就是堆結構
public class Heap {// 大根堆結構public static class MyMaxHeap {private int[] heap;private final int limit;private int heapSize;public MyMaxHeap(int limit) {heap = new int[limit];this.limit = limit;heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == limit;}public void push(int value) {if(heapSize == limit) {throw new RuntimeException("Heap is full!");}heap[heapSize] = value;heapInsert(heap, heapSize++);}public int pop() {if(heapSize == 0) {throw new RuntimeException("Heap is empty!");}int ans = heap[0];swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);return ans;}private void heapify(int[] heap, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 > heapSize ? left : (heap[left] > heap[left + 1] ? left : left + 1);largest = heap[largest] > heap[index] ? largest : index;if (largest == index) {return;}swap(heap, index, largest);index = largest;left = index * 2 - 1;}}private void heapInsert(int[] heap, int index) {while (heap[index] > heap[(index - 1) / 2]) {swap(heap, index, (index - 1) / 2);index = (index - 1) / 2;}}private void swap(int[] heap, int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}}// 參照組:暴力public static class RightMaxHeap {private int[] heap;private final int limit;private int heapSize;public RightMaxHeap(int limit) {heap = new int[limit];this.limit = limit;heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == limit;}public void push(int value) {if(heapSize == limit) {throw new RuntimeException("Heap is full!");}heap[heapSize++] = value;}public int pop() {if(heapSize == 0) {throw new RuntimeException("Heap is empty!");}int maxIndex = 0;for (int i = 1; i < heap.length; i++) {if(heap[maxIndex] < heap[i]) {maxIndex = i;}}int ans = heap[maxIndex];heap[maxIndex] = heap[--heapSize];return ans;}}public static void main(String[] args) {// 寫對數器驗證堆結構int value = 1000;int limit = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {int curLimit = (int)(Math.random() * limit) + 1;RightMaxHeap test = new RightMaxHeap(curLimit);MyMaxHeap my = new MyMaxHeap(curLimit);int curOpTimes = (int)(Math.random() * limit);for (int j = 0; j < curOpTimes; j++) {if (my.isEmpty() != test.isEmpty()) {System.out.println("Oops!");}if (my.isFull() != test.isFull()) {System.out.println("Oops!");}if (my.isEmpty()) {int curValue = (int)(Math.random() * value);my.push(value);test.push(value);}else if (my.isFull()) {if(my.pop() != test.pop()) {System.out.println("Oops!");}}else {if(Math.random() < 0.5) {int curValue = (int)(Math.random() * value);my.push(value);test.push(value);}else {if(my.pop() != test.pop()) {System.out.println("Oops!");}}}}}System.out.println("Finish!");}
}
1.2 改進的堆結構
為什么要改進?
- 原始堆,傳進去的東西比如
Student
類,我不修改這個類的任何值,用原始堆沒問題。 - 但是要是想把傳進去的
Student
類修改一下,比如修改年齡或者id,那么就必須要使用改進的堆。 - 改進的堆增加
resign
方法,可以在修改已經在堆里面的值之后還能形成堆結構。
改進的堆:
public class MyHeap<T> {private ArrayList<T> heap;private HashMap<T, Integer> indexMap;private int heapSize;private Comparator<? super T> comparator;public MyHeap(Comparator<? super T> comparator) {heap = new ArrayList<>();indexMap = new HashMap<>();heapSize = 0;this.comparator = comparator;}public boolean isEmpty() {return heapSize == 0;}public int getHeapSize() {return heapSize;}public void push(T value) {heap.add(value);indexMap.put(value, heapSize);heapInsert(heapSize++);}public T poll() {T ans = heap.get(0);int end = heapSize - 1;swap(0, end);heap.remove(end);indexMap.remove(ans);heapify(0, --heapSize);return ans;}public void resign(T value) {int valueIndex = indexMap.get(value);heapify(valueIndex, heapSize);heapInsert(valueIndex);}private void heapify(int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = (left + 1 < heapSize) && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0) ? left + 1 : left;largest = (comparator.compare(heap.get(largest), heap.get(index)) < 0) ? largest : index;if (largest == index) {return;}swap(largest, index);index = largest;left = index * 2 + 1;}}private void heapInsert(int index) {while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {swap(index, (index - 1) / 2);index = (index - 1) / 2;}}private void swap(int i, int j) {T o1 = heap.get(i);T o2 = heap.get(j);heap.set(i, o2);heap.set(j, o1);indexMap.put(o1, j);indexMap.put(o2, i);}
}
學生類:
public class Student {private int id;private String name;private int age;private String address;public Student() {}public Student(int id, String name, int age, String address) {this.id = id;this.name = name;this.age = age;this.address = address;}/*** 獲取* @return id*/public int getId() {return id;}/*** 設置* @param id*/public void setId(int id) {this.id = id;}/*** 獲取* @return name*/public String getName() {return name;}/*** 設置* @param name*/public void setName(String name) {this.name = name;}/*** 獲取* @return age*/public int getAge() {return age;}/*** 設置* @param age*/public void setAge(int age) {this.age = age;}/*** 獲取* @return address*/public String getAddress() {return address;}/*** 設置* @param address*/public void setAddress(String address) {this.address = address;}public String toString() {return "Student{id = " + id + ", name = " + name + ", age = " + age + ", address = " + address + "}";}
}
測試:
public class test {public static void main(String[] args) {Student s1 = new Student(1, "張三", 18, "西安");Student s2 = new Student(2, "李四", 20, "重慶");Student s3 = new Student(3, "王五", 19, "成都");Student s4 = new Student(4, "趙六", 22, "深圳");Student s5 = new Student(5, "錢七", 21, "北京");MyHeap<Student> myHeap = new MyHeap<>(new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {return o2.getId() - o1.getId();}});myHeap.push(s1);myHeap.push(s2);myHeap.push(s3);myHeap.push(s4);myHeap.push(s5);System.out.println(myHeap.isEmpty());System.out.println(myHeap.getHeapSize());System.out.println("====================");s1.setId(15);myHeap.resign(s1);while (!myHeap.isEmpty()) {System.out.println(myHeap.poll().toString());}}
}
2 前綴樹
可以完成前綴相關的查詢
2.1 前綴樹的結構
- 單個字符串中的字符從前到后加到一顆多叉樹上
- 字符放在路上,節點上有專屬的數據項(常見的是pass和end)
- 所有樣本都這樣添加,如果沒有路就新建,如果有路就復用
- 沿途所有的經過的節點的pass值加1,每個字符串結束時來到的節點的end值加1
// Node和TrieTree結合使用,Node2和TrieTree2結合使用。
// TrieTree2只能加入小寫字符組成的字符串,有局限性
// TrieTree可以都加入
public class TrieTreeSearch {public static class Node {public int pass;public int end;public HashMap<Integer, Node> next;public Node() {pass = 0;end = 0;next = new HashMap<>();}}public static class TrieTree {private final Node root;public TrieTree() {root = new Node();}public void insert(String word) {if (word == null) {return;}Node node = root;node.pass++;char[] chars = word.toCharArray();int index = 0;for (char aChar : chars) {index = aChar;if (!node.next.containsKey(index)) {node.next.put(index, new Node());}node = node.next.get(index);node.pass++;}node.end++;}public void delete(String word) {if (search(word) != 0) {Node node = root;node.pass--;int index = 0;char[] chars = word.toCharArray();for (char aChar : chars) {index = aChar;if (node.next.containsKey(index)) {node = node.next.get(index);}node.pass--;}node.end--;}}public int search(String word) {return research(word).end;}public int prefixNum(String word) {return research(word).pass;}private Node research(String word) {if (word == null) {return new Node();}Node node = root;char[] chars = word.toCharArray();int index = 0;for (char aChar : chars) {index = aChar;if (!node.next.containsKey(index)) {return new Node();}node = node.next.get(index);}return node;}}public static class Node2 {public int pass;public int end;public Node2[] next;public Node2() {pass = 0;end = 0;next = new Node2[26];}}public static class TrieTree2 {private final Node2 root;// 無參構造public TrieTree2() {root = new Node2();}// 添加字符串public void insert(String word) {if (word == null) {return;}char[] chars = word.toCharArray();Node2 node = root;node.pass++;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {node.next[index] = new Node2();}node = node.next[index];node.pass++;}node.end++;}// 查找字符串有多少個public int search(String word) {if (word == null) {return 0;}char[] chars = word.toCharArray();Node2 node = root;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {return 0;}node = node.next[index];}return node.end;}// 刪除字符串public void delete(String word) {if (search(word) != 0) {Node2 node = root;node.pass--;int index = 0;char[] chars = word.toCharArray();for (char aChar : chars) {index = aChar - 'a';if (--node.next[index].pass == 0) {node.next[index] = null;return;}node = node.next[index];}node.end--;}}// 有幾個字符串前綴是wordpublic int prefixNum(String word) {if (word == null) {return 0;}char[] chars = word.toCharArray();Node2 node = root;int index = 0;for (char aChar : chars) {index = aChar - 'a';if (node.next[index] == null) {return 0;}node = node.next[index];}return node.pass;}}public static String generateRandomString(int strLen) {char[] ans = new char[(int) (Math.random() * strLen) + 1];for (int i = 0; i < ans.length; i++) {int value = (int) (Math.random() * 26);ans[i] = (char) (value + 97);}return String.valueOf(ans);}public static String[] generateRandomString(int arrLen, int strLen) {String[] ans = new String[(int) (Math.random() * arrLen) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = generateRandomString(strLen);}return ans;}// 寫對數器進行測試public static void main(String[] args) {int strLen = 20;int arrLen = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {String[] strings = generateRandomString(arrLen, strLen);TrieTree my = new TrieTree();TrieTree2 test = new TrieTree2();for (String word : strings) {double decide = Math.random();if (decide < 0.25) {my.insert(word);test.insert(word);} else if (decide < 0.5) {my.delete(word);test.delete(word);} else if (decide < 0.75) {int ans1 = my.search(word);int ans2 = test.search(word);if(ans1 != ans2) {System.out.println("Oops!");}}else {int ans1 = my.prefixNum(word);int ans2 = test.prefixNum(word);if (ans1 != ans2) {System.out.println("Oops!");}}}}System.out.println("Finish!");}
}