♚ \
Author: Wei Ziyang, understand some code. wzy-codify.com
Blog: zhuanlan.zhihu.com/p/85518062
Preface: * * * *
Given an unordered array of length n and any number k, find the nearest m number to k (k may not appear in the array)
The topic is actually very simple, after thinking for a while gave a scheme as follows:
My train of thought ****
First, open up a new array D1, representing the distance between the array and k, use the absolute value of the way to calculate the distance (the first element is the distance, the second element is itself), and then fast-sort, and then take the first m elements in D1, the code implementation is as follows:
if __name__ == "__main__":
n = 15
k = 5
m = 5
li = [1.5.3.2.6.7.1.4]
print('The elements in the list:', li)
def solution1(li, k, m):
new_li = [(abs(each - k),each) for each in li]
new_li.sort(key=lambda a: a[0])
return [each[1] for each in new_li[:m]]
result = solution1(li, k, m)
print(result)
Copy the codeCan think of the complexity of this algorithm is n + nlogn, this method can be, but obviously not the best solution, the interviewer prompted several times, because just look at people used before, but no system study, finally didn’t think of pile is used to solve this problem, shame-awareness after yong, back immediately after carefully watched it again this knowledge.
What is the heap ****
A heap is a complete binary tree, and just to review the definition of a complete binary tree, the form of a complete binary tree is that all nodes are full except for the last layer, and all nodes in the last layer are to the left. The textbook defines it as follows:
If the depth of the binary tree is set as H, except for the h layer, the node number of all other layers (1 ~ H-1) reaches the maximum number, and all nodes of the h layer are continuously concentrated on the left, which is a complete binary tree.
The following figure shows a typical complete binary tree:
And the minimum heap requires that, for any parent, its children be larger than the parent, and similarly, the maximum heap means that its children are smaller than the parent. Obviously the figure above is not a minimum heap, but the figure below is:
Implementation of the heap ****
I said that the heap is a complete binary tree, but does that mean we really need to represent it as a tree? The answer is no, because a complete binary tree has the remarkable property that for the ordinal number n of any parent node (where n counts from 0), its children must have Ordinal Numbers 2n+1,2n+2, so we can represent a heap directly as an array. So for the figure above, we can use [0,1,3,2,4,6,7,8,9,5,10] to represent the heap.
In addition, all operations on the heap must remain a heap after the operation, and based on this principle, we implement operations on the heap. We initialize a heap as follows:
class Heap(object) :def __init__(self.array) :self.array = array
def __str__(self):
return str(self.array)
def __len__(self):
return len(self.array)
Copy the code1. Insert the Insert (push) * * * *
Here I’ve drawn a diagram where when a new element wants to be inserted into the heap, we put it first at the end of the heap. Then, according to the features of the heap, to adjust its position, because want to maintain the value of the parent node must never less than its value, and 2 of the 6 is greater than its parent node directly, so to put them to the position of the two exchange, exchange, and check the status of the heap, found his father node 3 is still greater than themselves, so continue to upgrade and 3 exchange, after compared to zero, Zero is not greater than itself, so stay where you are, end of insertion.
Simply put, to insert a node is to insert the element at the end of the heap, and then float up and down until the heap condition is satisfied.
The code implementation is as follows: the index parameter of push is len(self.array)
def insert(self, num, index):
self.array.append(num)
parent_index = index / / 2
while parent_index >= 0 and self.array[parent_index] > num:
self.array[parent_index], self.array[index] = self.array[index], self.array[parent_index]
if parent_index == 0:
break
index = parent_index
parent_index = parent_index / / 2
Copy the code2. Delete the pop
As shown in the figure below and delete elements are generally refers to delete the pile top, at the top of the heap element is removed, the element will be the end of the replacement, and then carries on the sinking operation, as this is the minimum pile and pile cap must be the smallest element, the first 1, 6 is greater than the left nodes need to sink, sink after continue to compare and its child nodes, found the left node 2 smaller than itself, continued to sink, Finally 8 and 9 are bigger than 6, stop sinking. To summarize, this means deleting the top element of the heap, replacing it with the bottom element, and then sinking until the heap condition is satisfied.
The code looks like this, first defining the sink method and then implementing pop on top of it:
def sink(self, index, array):
left_node_index = index * 2 + 1
right_node_index = index * 2 + 2
if left_node_index < len(array):
left_v = array[left_node_index]
if right_node_index >= len(array):
min_value = left_v
min_index = left_node_index
else:
right_v = array[right_node_index]
if left_v < right_v:
min_value = left_v
min_index = left_node_index
else:
min_value = right_v
min_index = right_node_index
if array[index] > min_value:
array[index], array[min_index] = array[min_index], array[index]
self.sink(min_index, array)
self.array[:len(array)] = array
def pop(self):
end_v = self.array.pop()
min_value = self.array[0]
self.array[0] = end_v
self.sink(0, self.array)
return min_value
Copy the code3. Build the heap
The process of building the heap is also very simple. Sink each parent node to complete the heap. So our Heap class can become:
def __init__(self, array):
self.array = array
for index in range(len(array)/ / 2-1, 1, 1) :
self.sink(index, self.array)
Copy the codeUse the heap idea
Had finished above the basic operations of a reactor, tell me the pile below is how to link to this topic, in short, if the reactor, we can maintain a maximum heap of length m directly, and then to traverse the list of the length is n li, every traverse the element and the element of distance and k tuples plug into the heap, When the length of the heap is greater than m, the largest element pops out (the most distant element), which means that the largest heap is always reserved for the m elements closest to K. Since both delete and insert are logm, the final algorithm is nlogm. Note that since m is definitely less than n, this algorithm is definitely faster than the previous sorting algorithm. The complete code is as follows:
class MaxHeap(object) :def __init__(self.array) :self.array = array
for index in range(len(array)/ / 2-1, 1, 1) :
self.sink(index, self.array)
def sink(self, index, array):
left_node_index = index * 2 + 1
right_node_index = index * 2 + 2
if left_node_index < len(array):
left_v = array[left_node_index]
if right_node_index >= len(array):
max_value = left_v
max_index = left_node_index
else:
right_v = array[right_node_index]
if left_v[0] > right_v[0]:
max_value = left_v
max_index = left_node_index
else:
max_value = right_v
max_index = right_node_index
if array[index] < max_value:
array[index], array[max_index] = array[max_index], array[index]
self.sink(max_index, array)
self.array[:len(array)] = array
def insert(self, num, index):
self.array.append(num)
parent_index = index / / 2
while parent_index >= 0 and self.array[parent_index][0] < num[0]:
self.array[parent_index], self.array[index] = self.array[index], self.array[parent_index]
if parent_index == 0:
break
index = parent_index
parent_index = parent_index / / 2
def push(self, num):
self.insert(num, len(self.array))
def delete(self):
end_v = self.array.pop()
self.array[0] = end_v
self.sink(0, self.array)
def sort(self):
for index in range(len(self.array)-1.0, -1):
self.array[0], self.array[index] = self.array[index], self.array[0]
self.sink(0, self.array[:index])
def __str__(self):
return str(self.array)
def __len__(self):
return len(self.array)
if __name__ == "__main__":
n = 15
k = 5
m = 5
li = [1.5.3.2.6.7.1.4]
print('The elements in the list:', li)
def solution2(li, k, m):
max_heap = MaxHeap([])
for num in li:
dis = abs(num-k)
max_heap.push((dis, num))
if len(max_heap) > m:
max_heap.delete()
return [each[1] for each in max_heap.array]
result = solution2(li, k, m)
print(result)
Copy the codeOther applications of heap ****
PriorityQueue is A Python PriorityQueue. PriorityQueue is A Python PriorityQueue. PriorityQueue is A Python PriorityQueue. Otherwise, after A search is implemented, even its bottom heap is not known).
In addition, the heap can be used as a sort, by swapping the top element with the bottom element each time, and then heaping the heap (i.e. sinking the top element) until the heap is empty. The implementation code is as follows:
def sort(self):
for index in range(len(self.array)-1.0, -1):
self.array[0], self.array[index] = self.array[index], self.array[0]
self.sink(0, self.array[:index])
Copy the code