Questions tagged [heap]

A heap is a tree-based data structure that satisfies the heap property. For questions about memory allocated from the system heap, use the [memory-management] tag.

Filter by
Sorted by
Tagged with
0
votes
3answers
44 views

Could this be considered a valid mergesort? [closed]

I tried to do a mergesort function for an assignment without importing merge from heapq: ...
6
votes
2answers
7k views

Min & Max heap implementation

As follows I have implemented Min and Max heap data structure, using an array for storing elements. I would need a code review, please. Please, spare recommendations for generic implementation as they ...
2
votes
2answers
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. ...
4
votes
1answer
981 views

Generic min heap in C++

I have recently started programming in C++. I have coded in MATLAB and C in the past. The following code implements a min heap as a generic class in C++. I would like to get some feedback on the ...
4
votes
3answers
308 views

k th smallest element in row wise and column wise sorted matrix

Find the kth smallest element in row wise and column wise sorted element: Example: matrix[row][col] < matrix[row+1][col] matrix[row][col] < matrix[row][col+1] mat= 1 ...
0
votes
1answer
46 views

Binary Heap Order Fixing in Java

I am implementing a binary heap in Java. I've come to the point where I have to fix the heap ordering whenever a new node is being inserted to the heap. The code below fixes the heap ordering. I have ...
6
votes
1answer
922 views

Sorting almost sorted array with a minimum heap

I'm currently looking into the quickest way to sort an almost sorted array: Given an array of \$n\$ elements, where each element is at most \$k\$ away from its target position, devise an ...
8
votes
1answer
1k views

Python Heap Implementation

I made this snippet for reviewing my DS textbook. Is it okay to write iterative loops in function _upheap and _downheap? Any ...
8
votes
1answer
10k views

Implementing heap in Python

This is basically a straightforward heap implementation. I am just moving from C to Python and I wanted to make sure that I follow Python's best practices in general. This heap is supposed to support ...
7
votes
2answers
1k views

C++11 (or C++14?) max heap implementation with a simple example

I've been writing C++03 non-professionally for a long time, and I finally started to play around with C++11 and C++14. I decided to try my hand at implementing a data structure that I was previously ...
10
votes
3answers
2k views

My own little memory manager in C

I have implemented a simple version of malloc() and its associated functions, free(), ...
3
votes
0answers
128 views

Finding the maximal bottleneck in a 2D matrix from source to destination

I recently started solving programming challenges and this one is causing me performance trouble. The problem statement is the following: You are given a 2d matrix where each cell contains an ...
14
votes
7answers
1k views

Binary Heap where a comparison delegate is used

I currently have a Generic Implementation of a BinaryHeap. It must be able to maintain it's integrity with elements that may or may not implement ...
7
votes
3answers
1k views

Sort Characters By Frequency

I solved this problem. Problem Statement Given a string, sort it in decreasing order based on the frequency of characters. Example 1 Input: "tree" Output: "eert" ...
1
vote
1answer
215 views

Template binary heap with lambda function comparator C++

This heap will be used for A* search pathfinding in my 2D isometric game engine. It uses lambda functions (instead of std::less or ...
4
votes
1answer
640 views

Find the running median with 2 heaps

I wrote code to solve the running median challenge using 2 heaps, and I'd appreciate any and all feedback. Here is the problem: You have a list of numbers and are scanning them one by one. ...
6
votes
1answer
2k views

C++ Heap implementation

I'm on my way of understanding basic data structures and sorting algorithms through implementing them in c++. Post is followed of my implementation of Vector. I decided to weld the heap behaviour ...
3
votes
1answer
151 views

Generic Median Heap using PriorityQueues

I've implemented a generic data structure to keep track of the median in a streaming list of numbers. I was hoping to gather the community's feedback on code style and taste. ...
4
votes
1answer
1k views

Linked list implementation of binary heap insertion

Is this a correct linked list implementation of binary heap insertion? This is not a homework exercise. ...
5
votes
2answers
200 views

Continuous median in Ruby

I have written a program in Ruby which calculates the median of a streaming set of numbers dynamically. For each number that arrives, the median is calculated for all the numbers that have arrived so ...
3
votes
1answer
197 views

Efficient bookkeeping in heap

I'm trying to implement a heap using list data structure. I'd also like to keep track of the position of elements in the list in order to enable easy deletion. My implementation involves looping ...
5
votes
3answers
2k views

Indexed Fibonacci heap implementation

I implemented two versions of a Fibonacci heap one using a unordered map (mapping keys to their nodes) so that the client can call decrease in \$O(1)\$ average and ...
4
votes
2answers
2k views

Testing if array is heap

This method tests an array of integers satisfies to see if its a max binary heap. This means each node is greater than or equal to it's children each node has at most 2 children the leaf nodes are ...
1
vote
0answers
483 views

Generic Pairing Heap Performance

I have made a generic pairing heap library in C. Pairing heaps are one of the several heap variants with better asymptotic running times than standard binary heaps (others include Fibonacci heaps and ...
3
votes
2answers
4k views

Heap Implementation in C#

I am learning fundamental data structures, and I want to know if this is a valid implementation of a heap. Can any C# features be used to improve or extend the implementation? In addition to heapsort, ...
2
votes
1answer
548 views

(Min)Heap implementation

Being that I needed a min-heap implementation for a project, I implemented one. Now that it's finished I though about having a review for it. I'm interested in all aspects: readability, performance, ...
3
votes
1answer
157 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 ...
3
votes
2answers
151 views

Time Limit Exceeded for build_max_heap

This problem is from HackerEarth: The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an ...
5
votes
1answer
137 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* ...
-4
votes
1answer
671 views

Nim Game with Arrays [closed]

I am suppose was to incorporate arrays in my NIM game java code, so that we can allow the user to decide on how many heaps are in play. I am stuck and have no clue how to do so. Heap Class ...
6
votes
3answers
1k views

Max heap implementation in Kotlin

I wrote this class a while ago to learn Kotlin and heaps, so any tips (on either my code style or my heap algorithm) would be appreciated! ...
1
vote
2answers
4k views

Array-based MinHeap implementation in Java

This is my implementation of MinHeap in Java. ...
1
vote
0answers
102 views

Generic implementation of mutable binary heap

std::priority_queue does not support dynamically updating element priorities. This class template extends it by allowing updating priorities of elements in the heap....
1
vote
1answer
870 views

Generic implementation of SiftUp/Down operations on binary heap

Binary heap construction and maintenance boil down to the two basic operations: sift up and sift down. Following are generic template implementations of the two operations. Any comments are welcome. I'...
1
vote
2answers
298 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 ...
5
votes
3answers
808 views

Heapsort in Python

Please review the following in-place implementation of Heapsort in Python: ...
2
votes
1answer
123 views

Minimalist Tree

While working on a small project, I tried to implement a super simple tree class in C++. It supports an arbitrary number of branches from each node. In addition to general comments, my main concerns ...
4
votes
0answers
131 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 ...
11
votes
1answer
622 views

Binary heap performance optimization

I have implemented a binary heap as a exercise in data structures. I realize that I'm missing some useful functions (increase/decrease key for example) but I don't consider them interesting for the ...
2
votes
0answers
435 views

Min-Heap based priority queue class written in ES6

I would appreciate any feedback on syntax, naming convention, possible shortcuts, clarity of code and any other constructive feedback. This code was based off of the Priority Queue chapter in The ...
1
vote
2answers
2k views

Read characters from stdin into an resizeable array

As first steps in C, I'm trying to write a program that reads from stdin into an array allocated on the free store, until an exclamation mark ! is entered. The ...
1
vote
0answers
2k views

Min Heap Sort using Generics

Here is my working code for a min-heap sort using an Array-List. I would like any input as to areas that need additional refining and any areas that are against proper formatting/usage. Although not ...
15
votes
1answer
655 views

C# Treap implementation

I recently developed a simple treap data structure in C#. In the future, I may have the class extend IDictionary. For now, I only expose a public accessor and a ...
3
votes
1answer
524 views

N-ary heap implementation

NaryHeap as a generalization of binary heap. Each node has up to N children. A template specialization for N = 2 (BinaryHeap) ...
3
votes
1answer
206 views

d-ary heap in C

Now I have this d-ary heap data structure. Note that for d = 2 this is a binary heap. The client programmer specifies the value ...
5
votes
2answers
3k views

Merge k Sorted Arrays

Please review my answer for this interview question: Merge k sorted arrays, using min heap. ...
2
votes
2answers
484 views

Heapsort for arbitrary ranges in Java

I plan to work on Introsort, which requires a working implementation of heap sort. Also, the heap sort implementation must be able to sort arbitrary ranges within an array, which, in turn, requires ...
0
votes
1answer
140 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 ...
5
votes
1answer
567 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 \$...
6
votes
1answer
884 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. ...