All Questions
35 questions
8
votes
2
answers
409
views
Heap sort optimization
I tried to optimize heap sort algorithm. Instead of recursion, I used iteration:
...
- 121
5
votes
1
answer
87
views
Bidirectional Dijkstra d-ary heap
This is my very first data structure written in Perl for a d-ary heap:
...
- 29.8k
0
votes
1
answer
73
views
Assigning Tasks to Entities (or some other entity) based on Priority
Main Questions:
Is my runtime analysis correct?
Is my approach optimal or close to it?
Is there a better way and/or improvements?
Objective:
Write an algorithm to assign ...
- 41
1
vote
1
answer
214
views
Sink algorithm in Max Heap Correctness
I am trying to determine the correctness of a helper method within my MaxHeap class.
The goal of this helper method is, given the index of any node in the Max Heap, sink it to the correct level in the ...
- 41
2
votes
1
answer
259
views
Priority Queue implementation for top k frequent elements leetcode in Ruby
While working on the following leetcode problem: https://leetcode.com/problems/top-k-frequent-elements/ I used a Priority Queu implementation in Ruby. I have learned how to implement a Priority Queu ...
- 355
2
votes
0
answers
221
views
Implement priority queue as min-heap in python
The standard library heapq in python doesn't support updating keys as a public method, which makes it hard to be used as a priority queue. Although the official ...
- 256
2
votes
0
answers
165
views
Fibonacci Heap Implementation In Java
From my repository.
This is my first time implementing a Fibonacci Heap, and since it's pretty complicated (at least to me), I would like to check if it is all correct.
...
- 191
4
votes
3
answers
2k
views
Min heap without recursion
The code reads in integer array from user input and builds a minimum heap via an iterative scheme.
Are there any edge cases in which this approach would fail?
For the following test case/command ...
- 177
5
votes
3
answers
871
views
Repeatedly keep removing 2 smallest elements and add its sum back to the list and return newly inserted elements' total
I have a list of unsorted numbers. Each time, I need to remove 2 smallest numbers and insert back its sum into the list. Repeatedly do this till the 1 final element is remaining in the list.
Return ...
- 151
8
votes
4
answers
512
views
Binary Heap (list-based)
This is my first attempt at implementing a heap data structure and I've decided to cover the methods Peek, Pop, ...
- 1,940
0
votes
1
answer
182
views
17
votes
1
answer
18k
views
Min/Max Heap implementation in Python
I'm refreshing some of my datastructures. I saw this as the perfect opportunity to get some feedback on my code.
I'm interested in:
Algorithm wise:
Is my implementation correct? (The tests say so)
...
- 1,460
2
votes
1
answer
408
views
Optimisation suggestions for Min Heap
Can someone please optimisations for my implementation of min heap.Its performance is poor compared to the heapq module in python. My use case for the MinHeap class is 'N' insertions and extractions ...
- 23
3
votes
2
answers
4k
views
Min&Max Heap implementation in .NET
Overview
I was doing some performance optimization patterns when I stumbled upon PriorityQueue and I implemented for that reason ...
- 413
9
votes
1
answer
8k
views
Prim's Algorithm using heapq module in python
Implementing Prim's with a \$O(m\log n)\$ run time using heaps, similar to Dijkstra heap implementation. Where \$n\$ is the number of nodes, and \$m\$ is the number of edges. Using the ...
- 105
1
vote
2
answers
757
views
Finding the running median with 2 heaps [closed]
I am trying to solve running median problem in hackerrank https://www.hackerrank.com/challenges/ctci-find-the-running-median and below is my code
...
- 129
12
votes
3
answers
2k
views
Given some integers, return the k most frequent elements
Given a non-empty array of integers, return the k most frequent elements.
For example, given [1,1,1,2,2,3] and k = 2, return <...
- 539
2
votes
2
answers
1k
views
Binary Min Heap data structure implementation
After reading about heap I tried to implement the heap. Below is my code along with test. Any feedback with respect to correctness, performance is welcome.
...
- 65
3
votes
1
answer
197
views
Heap Sort implementation time complexity
I have implemented Heap sort, but i think the time complexity is more than (nlogn).
Could anyone explain me; what is wrong in my code which makes more time complexity.
I will be glad if the answer is ...
5
votes
1
answer
167
views
A* implementation is not running efficiently but gets correct result
I'm not entirely sure what code other people will need to see, if I miss something off that is important please leave me a comment and I will update it as soon as I possibly can.
I have coded an A* ...
- 53
2
votes
2
answers
458
views
Fibonacci heap in C - follow-up
(See the previous iteration.)
I have incorporated some points made by ChrisWue and refactored my Fibonacci heap implementation:
fibonacci_heap.h
...
- 29.8k
4
votes
1
answer
214
views
Heap update generic algorithms
In the standard library, there are no algorithms for element updates. This makes it unsuitable as a queue for a Dijkstra's algorithm, for example. Thus I implemented generic heap update functions with ...
- 446
5
votes
2
answers
3k
views
Merge k Sorted Arrays
Please review my answer for this interview question:
Merge k sorted arrays, using min heap.
...
- 208
0
votes
1
answer
166
views
Heap selection sort - follow-up
See the previous and initial iteration.
I got rid of Run objects and just maintain two integer arrays in the RunHeap: one for ...
- 29.8k
5
votes
1
answer
727
views
Heap selection sort in Java
See the next iteration.
I designed and implemented this adaptive heap sort in Java. It works as follows:
Copy the range to be sorted into auxiliary array \$A\$
Create an empty run heap \$H\$
Scan \$...
- 29.8k
6
votes
1
answer
1k
views
D-ary max heap implementation
I implemented a D-ary max heap backed by a vector for resizing. I would like to know any possible improvements in performance, design, and in the code in general.
...
- 2,944
-2
votes
1
answer
2k
views
kth smallest element in min heap [closed]
I am working on to find the kth smallest element in min heap. I have code for this whose complexity is \$O(k \log k)\$. I tried to improve it to \$O(k)\$.
...
2
votes
1
answer
3k
views
Binomial heap in Java
I have this implementation of a binomial heap providing insert, decrease-key and extract in logarithmic time.
MinPriorityQueue.java:
...
- 29.8k
2
votes
1
answer
167
views
A different implementation of Heap Sort
The following implementation is a bit different form the standard implementations I have read. Is it correct?
...
- 323
6
votes
3
answers
20k
views
Optimizing Dijkstra implementation using PriorityQueue in Java
I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it ...
- 223
2
votes
1
answer
2k
views
Binary HeapSort and Ternary HeapSort implementation
This is my take on binary and ternary heapsort implementation for a university assignment. The code works but I wonder if there are any mistakes or things to improve.
...
- 123
2
votes
2
answers
2k
views
Merge N sorted list
Given n sorted lists, merge them.
This is a fairly common question, attributed to plenty of interview question websites.
I'm looking for code-review, optimizations and best practices. I'm also ...
- 8,401
5
votes
2
answers
13k
views
Constraint Programming: Map color problem
I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor...
- 1,233
5
votes
1
answer
2k
views
A* search algorithm: open set and heap
I'm working on an A* search algorithm implemention and this is what I came up with for the open list:
...
- 454
5
votes
2
answers
8k
views
Min Heap implementation with Dijkstra's algorithm
I am implementing Dijkstra's Algorithm using Min Heap to speed up the code.
For a small number of nodes, the code is really running very fast. But for a large number of nodes, my code is throwing ...
- 439