Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve PriorityQueue to use the exact heap algorithm #28

Closed
samchon opened this issue Dec 12, 2018 · 0 comments
Closed

Improve PriorityQueue to use the exact heap algorithm #28

samchon opened this issue Dec 12, 2018 · 0 comments
Labels
enhancement New feature or request
Projects

Comments

@samchon
Copy link
Owner

samchon commented Dec 12, 2018

Until now, PriorityQueue class has used TreeMultiSet as source container. The heap algorithm has been implemented exactly and it also passes the test automation. In such reason, I think it's good time to improve the PriorityQueue class.

namespace std
{
    export class ProrityQueue<T>
    {
        private source_: TreeMultiSet<T>;

        public top(): T
        {
            return this.source_.end().prev().value;
        }

        public pop(): void
        {
            this.source_.erase(this.source_.end().prev());
        }
        public push(val: T): void
        {
            this.source_.insert(val);
        }
    }
}

From now on, the PriorityQueue class would utilize Vector object and heap algorithm as its source container and arrange method, like below:

namespace std
{
    export class ProrityQueue<T>
    {
        private source_: Vector<T>;
        private comp_: (x: T, y: T) => boolean;

        public top(): T
        {
            return this.source_.front();
        }

        public pop(): void
        {
            pop_heap(this.source_.begin(), this.source_.end(), this.comp_);
            this.source_.pop_back();
        }

        public push(val: T): void
        {
            this.source_.push_back(val);
            push_heap(this.source_.begin(), this.source_.end(), this.comp_);
        }
    }
}
@samchon samchon added this to To do in v2.1 Update Dec 12, 2018
@samchon samchon added enhancement New feature or request C++20 and removed C++20 labels Dec 12, 2018
@samchon samchon moved this from To do to On review in v2.1 Update Dec 12, 2018
@samchon samchon moved this from On review to Done in v2.1 Update Dec 12, 2018
@samchon samchon closed this as completed Dec 12, 2018
@samchon samchon moved this from Done to Patch in v2.1 Update Feb 12, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
No open projects
v2.1 Update
  
Patch
Development

No branches or pull requests

1 participant