Java collection extension series (a) | figure framework Java collection extension series (2) | index of Java collection extended series (3) | and check
1, the preface
It seems that there is no native index heap implementation in Java’s own collection, even the native ordinary heap, and the PriorityQueue PriorityQueue although can be used as a heap, although the bottom is using the idea of heap implementation, but it is still a queue system.
2. What is a heap
- Characteristic 1: The essence is
A complete binary tree - Character 2:
The value of each node is smaller or larger than the value of its children.- Greater than the value of the child node
The maximum heapAnd vice versa is calledThe minimum heap.
- Greater than the value of the child node
Two complete binary trees belong to the heap as shown below
3. Application scenarios of heap
The heap can quickly obtain a maximum or minimum value in a set with O(1) time complexity.
Application scenarios
- Generate a priority queue
- Computation TopN problem of large data volume
- Calculate the median and percentile of dynamic data set
- High-performance scheduled task executor
4. Principle of heap implementation
4.1 into the heap
Insert a node into the end of a complete binary tree. Insert the node directly to the end of a complete binary tree. It is much easier to insert a node into the end of an array. However, the second major feature of the heap may not be satisfied after insertion, so an up-float repair operation is required starting at the tail node
4.2 out of the heap
To exit the heap, you need to remove the top element of the heap, that is, the root node of a complete binary tree. In practice, the root node and the tail node are exchanged once, and then the tail node is removed. Then perform a float repair operation from the root node.
As shown in the figure below, the root node 16 is first swapped with the tail node 4, and then the tail node is deleted.
4.3 repair
A repair is a repair operation performed when the relationship between nodes in the heap is no longer sufficient for each node to be smaller or larger than the values of its left and right children. It is mainly divided into up-floating repair and sinking repair
4.3.1 Buoyancy Repair
The implementation of the float repair is to start from a node and constantly swap with the parent node, assuming the maximum heap, if the current node is larger than the parent node, then the node should float up, so swap the two values. And so on, the parent node continues to compare and swap with the grandfather node… Until the condition is satisfied or the root is reached.
4.3.2 Subsidence repair
If the current node is smaller than the child node, then the node should float down, so swap them. And so on, the child continues to swap with the grandchild… Until the condition is satisfied or the tail is reached.
Here’s a list of the biggest onesExit the top element of the heapThe operation and fromThe heap top node starts sinking repair operationThe process of
How does Java use the heap
-
Use the PriorityQueue instead of the heap. The element with the highest priority can be dequeued each time. Elements are prioritized by default in the natural order in which they are added, or you can specify a custom comparator when you create a constructor.
-
PriorityQueue is an unbounded queue, and if we want to keep only N elements, we need to control the size of the heap ourselves
5.1 the heap sort
// Priority queue can be used when the heap, default is not specified when the minimum heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//PriorityQueue
minHeap = new PriorityQueue<>((a,b)-> b-a); / / the maximum heap
// Add elements to the heap
int[] arr = {3.5.1.2.8.4};
for (int i = 0; i < arr.length; i++) {
minHeap.add(arr[i]);
}
// The heap structure is
/* 1, 2, 3, 5, 8, 4 */
1,2,3,4,5,8
while(! minHeap.isEmpty()){ Integer poll = minHeap.poll(); System.out.println(poll); }Copy the code5.1 Solving TopN Problem
To find the smallest number of K, we can use the largest heap, because every time we take out the largest heap, we take out the smallest heap. To find the largest number of K, you can use the smallest heap, because every time you get out of the heap you get out of the smallest heap, so what’s left of the heap is the largest.
The test uses the maximum heap to find the smallest K number
// Create the maximum heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);
// Add 100,000 numbers to the array
ArrayList<Integer> arrList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
arrList.add(i);
}
// Shuffle the array data
Collections.shuffle(arrList);
// Set the minimum number of K
int K = 10;
// Add elements to the heap
for (Integer value : arrList) {
if (maxHeap.size() < K){
maxHeap.add(value);
}else if (value < maxHeap.peek()){
// Find a smaller value and add it to the heapmaxHeap.remove(); maxHeap.add(value); }}// Get the smallest number of K
while(! maxHeap.isEmpty()){ Integer poll = maxHeap.poll(); System.out.println(poll); }Copy the codeThe test uses the minimum heap to find the maximum number of K
// Create the maximum heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
// Add 100,000 numbers to the array
ArrayList<Integer> arrList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
arrList.add(i);
}
// Shuffle the array data
Collections.shuffle(arrList);
// Set the minimum number of K
int K = 10;
// Add elements to the heap
for (Integer value : arrList) {
if (maxHeap.size() < K){
maxHeap.add(value);
}else if (value > maxHeap.peek()){
// Find a larger value and add it to the heapmaxHeap.remove(); maxHeap.add(value); }}// Get the smallest number of K
while(! maxHeap.isEmpty()){ Integer poll = maxHeap.poll(); System.out.println(poll); }Copy the code6. Index heap
- The index heap is actually a heap
- The data and index parts are stored separately, unlike the normal heap where each node holds an index that points to the actual object value. But building an index heap depends on the actual value of the object corresponding to the index to compare and exchange
The index heap structure is shown below
- Each node of a complete binary tree stores the value of Index, while data maintains the mapping between Index and actual value, and then constructs the heap according to the actual value of data during comparison and exchange
- In fact, the normal heap implementation is just a layer of mapping, the core implementation is almost the same.
Compare with a normal heap
- Normal heaps can be time-consuming in swap operations, indexed heaps
Optimized the consumption of exchange elements. - It’s hard to index, it’s hard to change, but an indexed heap can index specific elements at level 0 (1),
That is, it supports very easy operations to modify heap elements - with
O(1) level access by indexAnd the characteristics of heap fast extraction extremum. - You could even say yes
A Map with heap functionality, but the heap is built based on the value of the index rather than the index.
6.1 Index heap implementation code
/** index heap *@author burukeyou
* @param* < KEY > index@param<VALUE> Indicates the VALUE of the index */
public class IndexHeap<KEY.VALUE extends Comparable<VALUE>> {
// The actual index tree keyTree[subscript I] = index
private ArrayList<KEY> keyTree;
// Map< index >
private Map<KEY,Integer> keyIndexMap;
// Map< index, element >
private Map<KEY, VALUE> keyDataMap;
// Whether the minimum heap
private boolean isMinHeap;
// Maximum capacity of the heap
private Integer maxSize;
public IndexHeap(boolean isMinHeap) {
this.isMinHeap = isMinHeap;
this.keyTree = new ArrayList<>();
this.keyIndexMap = new HashMap<>();
this.keyDataMap =new HashMap<>();
}
public IndexHeap(boolean isMinHeap, Integer maxSize) {
this(isMinHeap);
this.maxSize = maxSize;
}
public int size(a) {
return keyTree.size();
}
public boolean isEmpty(a) {
return keyTree.isEmpty();
}
public VALUE get(KEY key) {
return keyDataMap.get(key);
}
public boolean containsKey(KEY key) {
return keyDataMap.containsKey(key);
}
/** * replaces the index value *@param key
* @param e
*/
public void replace(KEY key, VALUE e) {
if(! keyDataMap.containsKey(key)){return;
}
keyDataMap.put(key, e);
// Get the node corresponding to the index
int j = keyIndexMap.get(key);
// Start from node j to repair the heap
moveUp(j);
moveDown(j);
}
/** * view the heap top element */
public Entry<KEY,VALUE> peek(a) {
KEY key = keyTree.get(0);
VALUE value = keyDataMap.get(key);
return new Entry<>(key,value);
}
/** * the top element of the heap is out of the heap */
public Entry<KEY,VALUE> remove(a) {
if (isEmpty()){
return null;
}
Entry<KEY,VALUE> ret = peek();
//1. Swap index values between tail node and heap header
swap(keyTree,0,size()-1);
/ / update
keyIndexMap.put(keyTree.get(0),0);
KEY lastKey = keyTree.get(size() - 1);
keyIndexMap.remove(lastKey);
keyDataMap.remove(lastKey);
keyTree.remove(size() - 1);
// Float down from the top of the heap
moveDown(0);
return ret;
}
/** * heap (index KEY does not exist) *@paramThe key indexes *@paramE actual value */
public void add(KEY key, VALUE e) {
if(! keyDataMap.containsKey(key)) { keyTree.add(key); keyDataMap.put(key, e); keyIndexMap.put(key, size() -1);
moveUp(size() - 1); }}/** * heap (replace index KEY if it exists) *@paramThe key indexes *@paramE actual value */
public void addOrReplace(KEY key, VALUE e){
if(! keyDataMap.containsKey(key)){ add(key,e); }else{ replace(key,e); }}/** * Float up from I to fix the heap *@paramI The subscript of the node in the index tree */
private void moveUp(int i) {
while (i > 0){
VALUE iValue = getValueByIndex(i);
VALUE parentValue = getValueByIndex(parent(i));
/ / the minimum heap
if (isMinHeap && iValue.compareTo(parentValue) > 0) {break;
}
/ / the maximum heap
if(! isMinHeap && iValue.compareTo(parentValue) <0) {break;
}
intpatentIndex = parent(i); swapAndRestKeyIndexMap(keyTree,i,patentIndex); i = parent(i); }}public VALUE getValueByIndex(int index){
return keyDataMap.get(keyTree.get(index));
}
/** * Float down from I to fix the heap *@paramI The subscript of the node in the index tree */
private void moveDown(int i) {
// Whether there is a child node, because it is a complete binary tree, only the left child can be determined
while(leftChildren(i) < size()) {
// point to a larger or smaller child node
int tempMin = leftChildren(i);
int rightIndex = tempMin + 1;
// Check whether the right child exists
if (rightIndex < size()){
// The smallest heap, if the right child is smaller than the left child, the tempMin pointer is updated
if (isMinHeap && getValueByIndex(tempMin).compareTo(getValueByIndex(rightIndex)) > 0){
tempMin = rightIndex;
}
If the right child is larger than the left child, update the tempMin pointer
if(! isMinHeap && getValueByIndex(tempMin).compareTo(getValueByIndex(rightIndex)) <0){ tempMin = rightIndex; }}// Compare with the parent node to determine whether swap is needed. If no swap is needed, the heap structure is adjusted and repaired.
if (isMinHeap && getValueByIndex(i).compareTo(getValueByIndex(tempMin)) <= 0) {break;
}
if(! isMinHeap && getValueByIndex(i).compareTo(getValueByIndex(tempMin)) >=0) {break;
}
//
swapAndRestKeyIndexMap(keyTree,i,tempMin);
// Update the parent nodei = tempMin; }}// Get the parent node
private int parent(int index){
return (index-1) /2;
}
// Get the left child node
private int leftChildren(int index){
return index * 2 + 1;
}
// Obtain second node
private int rightChildren(int index){
return index * 2 + 2;
}
// Swap indexes I and j in the index heap
private void swap(ArrayList<KEY> arr, int i, int j) {
KEY tmp = arr.get(i);
arr.set(i,arr.get(j));
arr.set(j,tmp);
}
Swap indexes I and j in the index heap and update the keyIndexMap relationship
private void swapAndRestKeyIndexMap(ArrayList<KEY> arr, int i, int j) {
KEY tmp = arr.get(i);
arr.set(i,arr.get(j));
arr.set(j,tmp);
keyIndexMap.put(keyTree.get(i),i);
keyIndexMap.put(keyTree.get(j),j);
}
/** * TopN computation encapsulation *@param key
* @param e
*/
public void addForTopN(KEY key, VALUE e){
if (maxSize == null || size() < maxSize){
// No threshold is specified, or the threshold is not reached
add(key,e);
return;
}
// The heap size is specified and the maximum heap element size is required
Entry<KEY, VALUE> topEntry = peek();
if (isMinHeap && e.compareTo(topEntry.getValue()) > 0) {// Find a larger number and add it to the heap
this.remove();
this.add(key,e);
}else if(! isMinHeap && e.compareTo(topEntry.getValue()) <0) {// Find a smaller number and add it to the heap
this.remove();
this.add(key,e); }}/** * check heap status */
public void output(a){
List<Entry<KEY,VALUE>> ret = new ArrayList<>();
for (KEY key : keyTree) {
VALUE value = keyDataMap.get(key);
ret.add(newEntry<>(key,value)); } ret.sort(Comparator.comparing(Entry::getValue)); ret.forEach(System.out::println); }}Copy the code/ * * *@author burukeyou
*/
public class Entry<KEY.VALUE> {
private KEY key;
private VALUE value;
public Entry(KEY key, VALUE value) {
this.key = key;
this.value = value;
}
public KEY getKey(a) {
return key;
}
public VALUE getValue(a) {
return value;
}
public void setKey(KEY key) {
this.key = key;
}
public void setValue(VALUE value) {
this.value = value;
}
@Override
public String toString(a) {
return "{" +
"'key':" + key +
", 'value':" + value +
'} '; }}Copy the code6.2 test
Heap sort
// Create the minimum index heap with the following parameters: true- minimum heap, false- maximum heap
IndexHeap<Integer, String> indexMinHeap = new IndexHeap<>(true);
// Add elements to the index heap
for (int i = 0; i < 10; i++) {
indexMinHeap.add(i, "Robot"+i);
}
// Change the value of the element with index 3 in the index heap
indexMinHeap.replace(3."Robot 9999999");
// View the heap top element
Entry<Integer, String> peek = indexMinHeap.peek();
/ / out of the heap
while(! indexMinHeap.isEmpty()){ Entry<Integer, String> tmp = indexMinHeap.remove(); System.out.println(tmp); }Copy the codeCalculate the TopN
- There is a scene where new users are added every day, and the lucky value will be assigned to each user at the beginning. The top ten lucky users need to be calculated in real time, and the command is received midway to adjust the user with the highest lucky value to 888888888.
// create a minimum index heap and set the heap size to 10
IndexHeap<Integer, Integer> indexMinHeap = new IndexHeap<>(true.10);
// 1, add 10000 users, assign a random lucky value
for (int i = 0; i <= 10000; i++) {
indexMinHeap.addForTopN(i,new Random().nextInt(10000));
}
// 2. The user with the highest lucky value will get a special reward, and the lucky value will be adjusted to 888888888
Integer maxUserId = indexMinHeap.peek().getKey(); // The id of the user with the highest score
System.out.println("将用户: " + maxUserId + "Lucky set to 888888888.");
indexMinHeap.replace(maxUserId,888888888);
// 3. Another 20,000 users were added
for (int i = 10001; i <= 20000; i++) {
indexMinHeap.addForTopN(i,new Random().nextInt(100000));
}
// 4. Query the top 10 lucky users
System.out.println("======= lucky value ranking is as follows:"+ LocalDateTime.now() +"= = = = = = = = = = =");
indexMinHeap.output();
// 5. Add 10,000 new users
for (int i = 20001; i <= 30000; i++) {
indexMinHeap.addForTopN(i,new Random().nextInt(100000));
}
// 6. Query the top 10 lucky users
System.out.println("======= lucky value ranking is as follows:"+ LocalDateTime.now() +"= = = = = = = = = = =");
indexMinHeap.output();
Copy the code