It doesn't have to be your searches, it could have just been the fact that your phone recognized you were on a road trip and that people in your ad cohort tend to want to buy shoes while on road trips.
I've worked in algorithmic ad space before and I can say that I've never seen evidence of phones listening on conversations but I have seen plenty of evidence from years ago where all your other data is used to form a terrifyingly accurate profile.
We used to do dead reckoning and gps speed gait profiling and we would only need about a weeks worth of GPS data to know height, weight, sex, where you live, where you work, where your kids go to school etc.
We would take that data and cross reference that with data broker info to form a profile, put you in an ad cohort bin, and serve you up as a platform for ad matching services to match to ad campaigns, which get even further targeted.
Millions of dollars spent hyper targeting you but 99 times out of 100 the inaccurate campaign is paying more so they get the adspace but the one time the actual low paying hyper focused campaign gets through it's always scary how accurate it is.
tl;dr: Ad companies don't need to listen to your conversation to know what you want to buy, ads are usually inaccurate because the inaccurate campaign paid more