Closed Morwenn closed 5 years ago
Thanks for your advise. I should update those codes. \o/
The v2.1 update has adopted EASTL
's implementation.
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.
import * as std from "tstl";
function main(): void
{
let v: std.Vector
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
```typescript
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();
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:
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.Well, now it's up to you what you want to do :p