foreword
Usually in programming learning, we will come into contact with the tree structure of heap. This blog mainly discusses the most common binary heap, and compares it with Fibonacci heap and Binomial heap Do some comparisons.
Definition of Binary Heap
As the name suggests, a binary heap is a heap shaped like a binary tree, and it is a complete binary tree, but the underlying implementation is usually an array. Because if it is numbered from top to bottom, from left to right, starting from 1, it can just fill the front part of the array, and more importantly, it is simple and efficient, and the numbering is the array index at this time. The following figure is a maximum heap:
For the i-th node, its parent index is: i/2;
Its left child index is: 2i, and its right child index is: 2i + 1.
Characteristics and uses of binary heaps
There are two types of heaps: maximum heap and minimum heap. In the former, the parent node keyword is always larger than the left and right children, and the same is true for the left and right child heaps; the latter is the opposite.
The largest heap is used to implement the priority queue. According to the maximum heap and the minimum heap, there can be a minimum priority queue and a maximum priority queue.
In addition, it can also be used to implement heap sorting, which is not discussed in this blog.
Operations on Binary Heaps
1. insert: insert an element into the heap and maintain the characteristics of the heap;
2. maximum: returns the largest keyword in the heap;
3. extractMax: extract the largest keyword in the heap and keep the heap characteristics;
3. increaseKey: Increase the keyword value of a node and maintain the characteristics of the heap.
inset
Algorithm process:
1. Now a keyword is added at the end of the heap for infinitesimal elements;
2. Then call the increaseKey process to adjust it from bottom to top until the characteristics of the heap are maintained.
The time complexity is O(lgn).
maximum
Directly returns the element keyword at the root of the heap
extractMax
Algorithm process:
1. Write down the root node keyword, copy the last node to the root, and reduce the heap size by 1;
2. Compare the node and its left and right children, find the maximum node, and exchange with each other;
3. Take the exchanged node as the new root, that is, the sub-heap, and continue the above process;
4. Until the node itself is the maximum node, or has become a leaf, that is, has no children.
The above process is iterated from top to bottom. Since the tree height is O(lgn), the time complexity is O(lgn). The source code is given directly later.
increaseKey
The parameters of the algorithm are the handle (pointer or integer identifier, etc.) of a node in the heap and the new keyword
Algorithm process:
1. Compare the size of the keyword of the node and the new keyword. If the new keyword is not greater than the existing keyword, refuse to modify and terminate the program, otherwise go to 2;
2. After modifying the old keyword, compare the value of the node with the keyword value of the parent node, if it is greater than it, exchange it with each other, and continue to iterate upward;
3. If it is not greater than or has become the root, the program is terminated, and the characteristics are maintained.
The above process is performed from bottom to top. Since the tree height is O(lgn), the time complexity is O(lgn). Source code here later.
The details of binary heap implementation
1. The structure of the nodes in the heap
The underlying data structure we use is a vector array, and its node structure is as follows:
template <typename Key, typename Handle = void*>
struct node
{//heap node
Key key;//The heap keyword, usually the priority of the application object
Handle obj_handle;//The handle associated with this keyword points to an external application object, possibly a pointer, immutable
node(const Key &k, const Handle &h_) :key(k), obj_handle(h_){}
node() :key(), obj_handle(){}<pre class="cpp" name="code"> Handle getHandle()const { return obj_handle; }
};As mentioned in "Introduction to Algorithms", a heap node usually only needs two elements, one is the priority (key), and the other is the handle of the external object, usually a pointer, which can be very convenient to interact with the external object, and later Example.
In this structure, the default type of Handle is void*. Usually, the exact type must be specified in application, but if only a single keyword is stored in the heap, it is not necessary to specify.
Second, the heap structure
template <typename Key,typename Handle = void*,class EditObjHandle = doNothing<Handle>,class CompareKey = greater<Key>>
class heap//The type parameters are keyword type, handle type, the handle of the external object corresponding to the edit heap node handle, and the comparator.
{//Binary heap, default max heap
private:
typedef node<Key, Handle> node;
vector<node> h;
int size;//heap size
EditObjIndex editIndex;
CompareKey compare;
};
The type parameter that needs to be highlighted is the third parameter EditObjHandle - when maintaining the characteristics of the heap, we need to move the nodes in the heap, then the node index associated with the external object must change, so through this function object we can easily The index is kept consistent through obj_handle, and this function object is provided by the user.
The default type is doNothing<Handle>, its implementation is as follows:
template <typename Handle>
struct doNothing :public binary_function < Handle, int, void >
{//The default external object handle in the heap to modify the function object
void operator()(const Handle &hd, int h)
{//do nothing
return;
}
};
Yes, it doesn't do anything, so how to change the external object's in-heap node index must be defined by yourself. The benefit of this default definition is that it can be used when only a single keyword is stored without specifying it.
The last type parameter is used to indicate which strategy the nodes in the heap are sorted by, that is, to implement the minimum heap or the maximum heap. We implement the maximum heap by default.
Third, the relationship between heap nodes and external objects
External objects are usually of the form, as follows:
template <typename Value>
struct object
{//testing object
int node_index;//index in the heap
int priority;//priority
Value v;//value
object(int pri, const Value& vv) :heap_handle(0), v(vv), priority(pri){}//Initially, handle defaults to 0
};heap_handle is the index of the associated heap node; priority is the priority of the object, which is the key field key of the heap node; v is its value. Initially heap_handle is 0 (meaning empty), and it will be properly maintained in subsequent feature adjustments.
The interaction between them is as follows:
Among them, EditObjIndex can generally be in the following form:
template <typename Value>
struct editObjIdx :public binary_function < object<Value>*, int , void >
{//A custom in-heap handle function object that modifies the object
void operator()(object<Value> *p, int hh)
{
p->node_index = hh;
}
};
binary heap, Fibonacci heap,Binomial heap Comparison of the operation time of each mergeable heap, note: some operations of the binary heap are not implemented
Below, we give the final implementation source code with detailed comments.
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
//#define MINIMUM_HEAP_H
#ifdef MINIMUM_HEAP_H //If the value is defined
const static int EXTREAM = 0x7fffffff;//It indicates that the implementation of the minimum heap
#else
const static int EXTREAM = 0x80000000;
#endif
template <typename Key, typename Handle = void*>
struct node
{//heap node
Key key;//The heap keyword, usually the priority of the application object
Handle obj_handle;//The handle associated with this keyword points to an external application object, possibly a pointer, immutable
node(const Key &k, const Handle &h_) :key(k), obj_handle(h_){}
node() :key(), obj_handle(){}
Handle getHandle()const { return obj_handle; }
};
template <typename Handle>
struct doNothing :public binary_function < Handle, int, void >
{//The default external object handle in the heap to modify the function object
void operator()(const Handle &hd, int h)
{//do nothing
return;
}
};
template <typename Key,typename Handle = void*,class EditObjIndex = doNothing<Handle>,class CompareKey = greater<Key>>
class heap//The type parameters are keyword type, handle type, the handle of the external object corresponding to the edit heap node handle, and the comparator.
{//Binary heap, default max heap
private:
typedef node<Key, Handle> node;
vector<node> h;
int size;//heap size
EditObjIndex editIndex;
CompareKey compare;
public:
//Four different constructors
heap() :h(), editIndex(), compare(),size(0){}
heap(const EditObjIndex &eh) :editIndex(eh), compare(), h(), size(0){}
heap(const CompareKey &comp) :compare(comp), editIndex(), h(),size(0){}
heap(const EditObjIndex &eh, const CompareKey &comp) :editIndex(eh), compare(comp), h(), size(0){}
bool empty()const { return size == 0; }
size_t length()const { return size; }
Key maximum()const { return h[0].key; }//If it is a min heap, the min key is returned
void insert(const Key&,const Handle& = Handle());
Key extractMax();
void increaseKey(int, const Key&);
};
template <typename K,typename H,class EOH,class CK>
K heap<K, H, EOH, CK>::extractMax()
{//Extract the maximum value, and adjust the heap
K k = h[0].key;
h[0] = h[--size];//Put the last element at the root of the heap
editIndex(h[size].obj_handle, 0);//Modify the handle in the heap of the external object associated with this element
int left = 1, right = 2, i = 0, largest = i;
while (left < size)
{//Adjust the heap from top to bottom
if (left < size && compare(h[left].key, h[largest].key))
largest = left;
if (right < size && compare(h[right].key, h[largest].key))
largest = right;//determine the maximum value
if (largest == i) break;//If it is the largest, exit and no longer adjust
else
{//otherwise
std::swap(h[largest], h[i]);//swap two elements
//And modify the heap handle of the external object associated with these two elements
editIndex(h[largest].obj_handle, largest);
editIndex(h[i].obj_handle, i);
}
left = 2 * largest + 1, right = 2 * largest + 2,i = largest;//Modified to continue iterating
}
return k;//return the maximum value
}
template <typename K,typename H,class EOH,class CK>
void heap<K, H, EOH, CK>::increaseKey(int index, const K &k)
{//Increase the keyword value of the specified element, if it is a min heap, this function means to decrease the keyword value
if (!compare(k, h[index].key))
{//If the new keyword is not suitable
#ifdef MINIMUM_HEAP_H
cout << "Error:greater key" << endl;
#else
cout << "Error:less key" << endl;
#endif
return;
}
h[index].key = k;
int parent = (index - 1) / 2;
while (parent >= 0 && compare(k,h[parent].key))//If it is larger than the parent node
{//Tuning the heap from the bottom up
std::swap(h[index], h[parent]);
editIndex(h[parent].obj_handle, parent);
editIndex(h[index].obj_handle, index);
if (parent == 0) break;//If you have reached the root
else
{//Otherwise continue to iterate
index = parent;
parent = (index - 1) / 2;
}
}
}
template <typename K,typename H,class EOH,class CK>
void heap<K, H, EOH, CK>::insert(const K &k,const H &hd = H())
{//Insert elements, the parameters are the weight and unique identifier of the external object respectively
if (size == h.size()) h.resize(2 * size + 1);//if the vector is full
++size;
editIndex(hd, size - 1);
if (size == 1)//if the first element
h[size - 1] = node(k, hd);
else
{//otherwise
h[size - 1] = node(EXTREAM, hd);//if
increaseKey(size - 1, k);
}
}
//----------------------------------------test--------- ------------------------------
template <typename Value>
struct object
{//testing object
int node_index;//index in the heap
int priority;//priority
Value v;//value
object(int pri, const Value& vv) :node_index(0), v(vv), priority(pri){}//Initially, the index defaults to 0
};
template <typename Value>
struct editObjIdx :public binary_function < object<Value>*, int , void >
{//In-heap index function object of custom modified object
void operator()(object<Value> *p, int hh)
{
p->node_index = hh;
}
};
int main()
{
heap<int, object<int>*, editObjIdx<int>> h;
vector<object<int>*> vec;//store these obj
for (int i = 0; i <= 10; i += 2)
{//The weight of obj is 2*i, and the value is i*i
object<int> *p = new object<int>(2 * i, i * i);
vec.push_back(p);
h.insert(2 * i, p);
}
for (int i = 1; i <= 10; i += 2)
{
object<int> *p = new object<int>(2 * i, i * i);
vec.push_back(p);
h.insert(2 * i, p);
}
/*while (!h.empty())
cout << h.extractMax() << endl;
cout << endl;*/
for (size_t i = 0; i <= h.length(); i += 3)
{//Increase the weight of some objects
vec[i]->priority += 100;
h.increaseKey(vec[i]->node_index, vec[i]->priority);
}
while (!h.empty())
cout << h.extractMax() << endl;
for (int i = 0; i != vec.size(); ++i)
delete vec[i];
/*heap<int> h;//There is only a heap of keywords. At this time, Handle and EditObjIndex are default values. There is no so-called handle.
for (int i = 0; i != 10; ++i)
h.insert(i);
while (!h.empty())
cout << h.extractMax() << endl;*/
getchar();
return 0;
}