2

I have a lists of lists with two elements [A,B]. Firstly I want my heap to be defined in terms of A but in the case A = A I would like to compare B in decreasing order. But heapsort understandably also compares the B in increasing order when I want it in decreasing order, so ill get something like this

[7, 1]
[7, 0]
[6, 1]
[5, 2]
[5, 0]
[4, 4]

When I want this 

[7, 0]
[7, 1]
[6, 1]
[5, 0]
[5, 2]
[4, 4]

How could I accomplish this?

For reference I'm using heapq._heapify_max

The official python solution recommends turning everything into a tuple where the first element is the one I want the sort priority on, but since I want my sort to be done on a combination of two keys this will not work

Mitch
  • 3,342
  • 2
  • 21
  • 31
  • Possible duplicate of [heapq with custom compare predicate](https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate) – Jim Mischel Sep 28 '18 at 13:45
  • Just run a bubble sort using both values with your own comparison logic over the heap-sorted list. Not the perfect solution, but it seems there is no better for that module – Ilia Gilmijarow Sep 29 '18 at 00:06
  • @IliaGilmijarow bubble sort would be too costly for the time constraints. I just used a stable sorting algorithm and ran over it twice. I know there are other ways to solve the problem I was just wondering if there was a standard python solution for this – Mitch Sep 29 '18 at 01:13
  • Would bubble sort be costly on a pre-sorted list? I thought it performs very well in cuch cases... – Ilia Gilmijarow Sep 29 '18 at 11:52
  • @IliaGilmijarow I can't think of any case in which bubble sort will outperform insertion sort. Yes, both are O(n^2) algorithms, but insertion sort is generally faster in real world applications. But you're right, both of those algorithms perform well with pre-sorted lists. – Jim Mischel Sep 29 '18 at 18:00
  • @MitchelPaulin Why would you need to go over the list twice to sort it? Can't your comparison function compare the first element and, if they're equal, compare the second? I don't see how making two passes over the list will sort it correctly. – Jim Mischel Sep 29 '18 at 18:01
  • @JimMischel I used a stable sorting algorithm so the relative ordering stayed the same over both iterations – Mitch Sep 29 '18 at 19:59
  • @IliaGilmijarow the list isn't pre sorted. The list I was showing was a representation of the heap I constructed – Mitch Sep 29 '18 at 20:07
  • @JimMischel check out this https://en.wikipedia.org/wiki/Radix_sort for more information – Mitch Sep 29 '18 at 20:08

0 Answers0