Poplar heap is probably not what you want

[Morwenn]

I noticed that you use my poplar heap project to implement the heap algorithms. I don't have a problem with that, but it is probably not what you want:

• The C++ specification mandates that the heap algorithms use a max heap, and poplar heap is a different kind of heap altogether.
• The poplar heap as I implemented it doesn't give you O(1) access to the max element of the heap: it is extracted when calling pop_heap (which is a O(log n) operation) but is not available out-of-the-box as with a max heap. The poplar heap was described in a paper trying to implement a new kind of heapsort, so not having O(1) access to the max element didn't matter, but in the case of STL-like generic heap algorithms it surely matters, be it only to implement a priority queue.
• Even if poplar heap was fine, it is actually slower for pretty much everything than a max heap (and I tried to make it as fast as possible...), so it doesn't really offer anything ^^'

Well, now it's up to you what you want to do :p

[samchon]

Thanks for your advise. I should update those codes. \o/

[samchon]

The v2.1 update has adopted EASTL's implementation.

• https://github.com/electronicarts/EASTL/blob/master/include/EASTL/heap.h
• https://github.com/samchon/tstl/blob/v2.1/src/algorithm/heaps.ts

[samchon]

After adapting the EASTL's implementation, I tested the heap functions using example codes from the C++ guidances and the implementation worked exactly same with those examples. Thus, I consider that error has been fixed.

C++ Reference

• http://www.cplusplus.com/reference/algorithm/make_heap/

import * as std from "tstl";

function main(): void
{
	let v: std.Vector<number> = new std.Vector([10, 20, 30, 5, 15]);

	std.make_heap(v.begin(), v.end());
	console.log("initial max heap:", v.front());

	std.pop_heap(v.begin(), v.end());
	v.pop_back();
	console.log("max heap after pop", v.front());

	v.push_back(99);
	std.push_heap(v.begin(), v.end());
	console.log("max heap after push", v.front());

	std.sort_heap(v.begin(), v.end());

	console.log("final sorted range:", v.data());
}
main();

CPP Reference

• https://en.cppreference.com/w/cpp/algorithm/make_heap

import * as std from "tstl";

function main(): void
{
	let v: std.Vector<number> = new std.Vector();
	v.push(3, 1, 4, 1, 5, 9);

	console.log("initially, v:", v.data());

	std.make_heap(v.begin(), v.end());
	console.log("after make_heap:", v.data());

	std.pop_heap(v.begin(), v.end());
	console.log("largest element:", v.back());

	v.pop_back();
	console.log("after removing the largest element:", v.data());
}
main();