Введение в алгоритм больших данных

Посмотрите вверх

Подобно фильтру Buron, растровое изображение также обладает преимуществом быстрого просмотра. Поскольку фильтр Buron представляет собой отображение нескольких хэшей, он, несомненно, занимает больше места, чем использование bitmap для хранения большего пространства, но bitmap может гарантировать отсутствие конфликта хэшей. , bitmap является выбором, когда запрашиваемая частота ложных срабатываний как можно ниже.
В-третьих, куча и сортировка кучи
Я также участвовал в предыдущих заметках, но я был очень поверхностным. На этот раз я пришел к системе!
3.1 концепция
кучаЭто структура данных, имеющая "полное двоичное дерево" (в соответствии с промежуточным узлом в промежуточном узле), и по сравнению с полным двоичным деревом обладает следующими особыми свойствами: значение каждого узла больше или равно (меньше или равно). Ценность ребенка. Где значение каждого узла больше или равно левому и правому дочерним элементамБольшая верхняя кучаЗначение каждого узла меньше или равно левому и правому дочерним элементамКуча。

Рисунок 5 большой верхний стек с маленькой верхней кучей
Сортировка по стекуЭто метод, который использует кучу для сортировки, и в статьях есть история, обобщенная между методом сортировки.
3.2 Введение в алгоритм стекирования
Сортировка по кучам, по сути, является разновидностьюВыберите сортировку Каждый раз выбирайте максимальное (маленькое), второе (маленькое), третье большое (маленькое). . . Элементы. В общем случае при порядке возрастания используются большие верхние стеки, при последовательности убывания - маленькие верхние стеки; общие шаги для сортировки приведены ниже:

1. 
   Приводит к созданию неупорядоченного массива в кучу (большая вершина или маленькая вершина)
   
2. 
   Замените верхние элементы на неотсортированные последние элементы ([0, j])
   
3. 
   Перестроить кучу, диапазон [0, J]
   
4. 
   Перейдите к J-1, вернитесь к шагу 2, пока J не будет равно 0, все по порядку.
   

Ниже приводится множество записей на C ++:
#pragma once
// Stack Sort
#include"Sort.h"
class HeapSot : public Sort {
private:
/ / Establish a large root heap (starting from the second layer node to the node)
void buildHeap(int* _array,size_t _size) {
for (int i = (_size - 1) / 2; i >=0 ; i--) {
fixHeapNode(_array, i, _size);
}
}
/ / Maintain a large root pile point to ensure that the array from this node to the specified length is a large root (from the Node node down)
void fixHeapNode(int* _array, int node,size_t _size) {
int swapNode, lc=2 * node + 1, rc= 2 * node + 2;
while (lc < _size) {
if (rc<_size && _array[lc]<=_array[rc])
{
swapNode = rc;
}
else swapNode = lc;
if (_array[node] < _array[swapNode]) swap(_array[node], _array[swapNode]);
node++;
lc = 2 * node + 1, rc = 2 * node + 2;
}
}
public:
void sort(int* _array, size_t _size)override {
buildHeap(_array, _size);// Build a big root
for (int i = _size-1; i >=0; i--) {
/ / Switch the top and stacked tail each time, because it is a large root heap, the elements of the tail after exchange must be the largest!
swap(_array[0], _array[i]);
// Do not move the tail element, re-maintain the pile of top ~ (pile of one element), the purpose is to find the second largest element so that the next loop is placed in the back corresponding position.
fixHeapNode(_array, 0, i);
}
}
};

• 
  1
  
• 
  2
  
• 
  3
  
• 
  4
  
• 
  5
  
• 
  6
  
• 
  7
  
• 
  8
  
• 
  9
  
• 
  10
  
• 
  11
  
• 
  12
  
• 
  13
  
• 
  14
  
• 
  15
  
• 
  16
  
• 
  17
  
• 
  18
  
• 
  19
  
• 
  20
  
• 
  21
  
• 
  22
  
• 
  23
  
• 
  24
  
• 
  25
  
• 
  26
  
• 
  27
  
• 
  28
  
• 
  29
  
• 
  30
  
• 
  31
  
• 
  32
  
• 
  33
  
• 
  34
  
• 
  35
  
• 
  36