Introduction to Algorithms Chapter 6 Binary Heaps

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;
}







Tags: Algorithm C++ data structure

Posted by ch3m1st on Sun, 11 Sep 2022 22:22:31 +0530